Murakkablik tahlili
Algoritmning vaqt va xotira sarfi input hajmi (n) o‘sishi bilan qanday o‘zgarishini tahlil qilish. Intervyuning eng ko‘p so‘raladigan qismi — Big O notation.
Big O notation — O(1), O(log n), O(n), O(n²)
Nima bu?
Big O algoritmning eng yomon holatdagi vaqt murakkabligini ifodalaydi. Constant faktorlar va past darajali hadlar e’tiborga olinmaydi: O(2n + 5) → O(n). Asosiy darajalar: O(1) — doim bir xil vaqt, O(log n) — har qadamda qidiruv maydoni yarmiga qisqaradi, O(n) — bitta loop, O(n log n) — samarali saralash, O(n²) — ichma-ich loop.
Kod misoli
// O(1) — index bo'yicha olish
function getFirst(arr) {
return arr[0]
}
// O(n) — bitta loop
function sum(arr) {
let total = 0
for (const x of arr) total += x
return total
}
// O(n²) — ichma-ich loop
function hasDuplicateNaive(arr) {
for (let i = 0; i < arr.length; i++) {
for (let j = i + 1; j < arr.length; j++) {
if (arr[i] === arr[j]) return true
}
}
return false
}
// O(n) vaqt, O(n) xotira — Set bilan optimallashtirish
function hasDuplicate(arr) {
const seen = new Set()
for (const x of arr) {
if (seen.has(x)) return true
seen.add(x)
}
return false
}
// O(log n) — binary search (massiv tartiblangan bo'lishi kerak)
function binarySearch(arr, target) {
let left = 0
let right = arr.length - 1
while (left <= right) {
const mid = Math.floor((left + right) / 2)
if (arr[mid] === target) return mid
if (arr[mid] < target) left = mid + 1
else right = mid - 1
}
return -1
}
Imtihonda
- «Bu funksiyaning vaqt murakkabligi qanday? Nega?»
- «
O(n² + n)ni soddalashtiring» →O(n²) - «Duplicate topishni
O(n²)danO(n)ga qanday yaxshilaysiz?»
Yodlash uchun
Eng katta darajali had g‘alaba qiladi — ichma-ich loop ko‘pincha O(n²), hash map lookup odatda O(1).
Space complexity
Nima bu?
Space complexity algoritm ishlashi uchun qo‘shimcha xotira sarfi. Bu yangi massiv, hash map, rekursiya call stack kabi narsalarni o‘z ichiga oladi. Input o‘zi hisobga olinmaydi — faqat qo‘shimcha xotira. Masalan, in-place swap O(1) xotira, yangi massiv yaratish O(n).
Kod misoli
// O(1) qo'shimcha xotira — in-place teskari aylantirish
function reverseInPlace(arr) {
let left = 0
let right = arr.length - 1
while (left < right) {
;[arr[left], arr[right]] = [arr[right], arr[left]]
left++
right--
}
return arr
}
// O(n) qo'shimcha xotira — yangi massiv
function reverseCopy(arr) {
const result = []
for (let i = arr.length - 1; i >= 0; i--) {
result.push(arr[i])
}
return result
}
// O(n) xotira — frequency map
function countFrequency(arr) {
const freq = new Map()
for (const x of arr) {
freq.set(x, (freq.get(x) || 0) + 1)
}
return freq
}
// O(n) stack chuqurligi — rekursiv Fibonacci (vaqt ham O(2^n))
function fib(n) {
if (n <= 1) return n
return fib(n - 1) + fib(n - 2)
}
// Call stack chuqurligi: O(n)
Imtihonda
- «Bu yechimning space complexity qanday? In-place qilish mumkinmi?»
- «Rekursiya va iteratsiya space farqi nima?»
- «Two Sum uchun Map ishlatsangiz vaqt va xotira qanday?» →
O(n)vaqt,O(n)xotira
Yodlash uchun
Vaqt va xotira odatda trade-off: O(n) xotira bilan O(n²) vaqtni O(n) ga tushirish mumkin.