Ma'lumotlar Tuzilmalari15 daqiqa
Massivlar, Deque va Xesh-jadvallar (Hash Tables)
Algoritmlarda massivlar va lug'atlar bilan O(1) vaqtda ishlash, qidirish va Two Sum kabi masalalarni optimal yechish asoslari.
1. Massivlar va Vaqt murakkabligi
Pythondagi `list` dinamik massiv bo'lib: • Indeks bo'yicha murojaat: O(1) • Oxiriga element qo'shish (append): amortizatsiyalangan O(1) • Boshiga yoki o'rtasiga element qo'shish/o'chirish: O(N) (chunki qolgan barcha elementlar suriladi) Agar sizga navbat (Queue) kerak bo'lsa, `list` o'rniga `collections.deque` dan foydalaning. `deque.popleft()` O(1) vaqt oladi.
Python 3 namunasiUTF-8
from collections import deque
navbat = deque([1, 2, 3])
navbat.append(4) # O(1)
boshi = navbat.popleft() # O(1)
print(boshi) # 12. Xesh-jadval (dict va set) — O(1) Qidiruv
Xesh-jadval har qanday kalitni xesh-funksiya orqali indeksga aylantiradi. Bu orqali qiymatni qidirish, qo'shish va o'chirish o'rtacha O(1) vaqtda bajariladi. Bu xususiyat orqali Two Sum masalasini O(N^2) dan O(N) ga tushirish mumkin:
Python 3 namunasiUTF-8
def two_sum(nums, target):
seen = {}
for i, num in enumerate(nums):
diff = target - num
if diff in seen:
return [seen[diff], i]
seen[num] = i
return []
print(two_sum([2, 7, 11, 15], 9)) # [0, 1]