Space complexity — algoritm kirish hajmiga qarab qancha xotira talab qilishini ifodalovchi nazariy o‘lchovdir. U inputning o‘zi egallagan joy va hisoblash davomida ajratiladigan yordamchi xotirani farqlashi mumkin. Tahlilda qaysi ta’rif ishlatilgani aniq ko‘rsatiladi.
Auxiliary space
Auxiliary space algoritm inputdan tashqari qo‘shimcha ishlatadigan xotiradir. In-place algoritm ko‘pincha O(1) auxiliary space bilan ishlaydi, lekin input massivining O(n) joyi baribir mavjud. “In-place” mutlaq nol xotira degani emas.
Output hajmi ham ba’zan alohida hisoblanadi. Barcha permutationlarni chiqaruvchi algoritm natijaning o‘zi juda katta bo‘lgani uchun undan kam umumiy space ishlata olmaydi. Streaming output natijalarni birma-bir chiqarib, peak memory’ni kamaytiradi.
Stack va heap
Rekursiv chaqiruv har bir darajada stack frame saqlaydi. Depth n bo‘lsa hatto lokal ma’lumot doimiy bo‘lgan funksiya O(n) stack ishlatishi mumkin. Balanced tree recursion odatda O(log n), skewed tree esa O(n) chuqurlikka yetadi.
Heap’da collection, memoization table, graph visited set va temporary bufferlar saqlanadi. Garbage-collected tilda ishlatilmay qolgan obyekt darhol bo‘shamasligi sabab runtime peak nazariy live-set’dan kattaroq bo‘lishi mumkin.
Peak va jami allocation
Space complexity odatda bir vaqtdagi maksimal xotirani o‘lchaydi. Algoritm ketma-ket ko‘p temporary buffer yaratib bo‘shatsa, jami allocated bytes katta, peak esa kichik bo‘lishi mumkin. Allocation rate garbage collector va allocator overheadiga ta’sir qiladi.
Ikki phase bir xil O(n) buffer’ni navbat bilan ishlatsa peak O(n), O(2n) emas. Agar ikkalasi bir paytda tirik bo‘lsa ham asimptotik sinf o‘zgarmaydi, lekin constant amalda muhim.
Time-space tradeoff
Memoization oldingi natijalarni xotirada saqlab, takroriy hisoblashni kamaytiradi. Dynamic programming jadvali ko‘pincha vaqtni yaxshilab, O(n) yoki O(n²) space talab qiladi. Agar faqat oldingi qator kerak bo‘lsa rolling array space’ni kamaytiradi.
Compression xotirani tejaydi, lekin CPU sarfini oshiradi. Cache hisoblashni tezlashtiradi, ammo eviction va consistency talabini keltiradi. Tanlov xotira limiti, latency va input hajmiga asoslanadi.
Tizim darajasi
Virtual memory katta address space beradi, ammo physical RAM yetmasa page fault va swapping unumdorlikni keskin pasaytiradi. Memory limitli container OOM killer bilan tugashi mumkin. Nazariy bound deployment limitiga real byte hisobida tarjima qilinadi.
Data structure overhead — pointer, alignment, object header va allocator metadata — Big O’da yashirin qoladi. Packed array pointerli linked structure’dan ancha kam joy va yaxshiroq cache locality berishi mumkin. Profiler retained size, allocation site va peak RSSni o‘lchaydi.
Parallel algoritmlar
Parallel workerlar bir xil read-only inputni bo‘lishishi mumkin, ammo har workerga private buffer berilsa umumiy space worker_count × buffer_size bo‘ladi. Thread stacklari va task queue ham hisobga olinadi. Work stealing scheduler tugallanmagan task obyektlarini saqlaydi; juda mayda bo‘linish scheduling memory’sini oshiradi. Distributed algoritm har node xotirasini alohida va cluster bo‘yicha jami baholaydi. Data replication fault tolerance beradi, lekin space koeffitsientini oshiradi. Memory budget concurrency limit bilan birga belgilanmasa yuk ortganda nazariy per-request kichik buffer ham hostni tugatishi mumkin.
Bog‘liq tushunchalar
Time complexity, Auxiliary space, In-place algorithm, Stack space, Memoization, Memory profiling