So'zlikni ifodalovchi ma'lumotlar tuzilmasining o'rtasiga element qo'shish operatsiyasining vaqt murakkabligini qanday aniqlash mumkin?

Ma'lumotlar tuzilmasining o'rtasiga element qo'shish, lug'atni ifodalovchi ma'lumotlar tuzilmasining aniq amalga oshirilishiga bog'liq. Standart lug'atlardagi (masalan, Swift'dagi Dictionary yoki Objective-C'dagi NSDictionary) elementlar tartiblangan indeksga ega emas, shuning uchun "o'rtaga qo'shish" tushunchasi to'g'ridan-to'g'ri qo'llanilmaydi.

Agar ma'lumotlar tuzilmasi kalit-qiymat juftlarini tartiblangan holda saqlasa (masalan, juftliklar massiv), unda o'rtaga qo'shish uchun barcha keyingi elementlarni siljitish talab qilinadi, bu esa vaqt murakkabligi O(n) ga teng, bu yerda n - qo'shish pozitsiyasidan keyingi elementlar soni.

Hash jadvallari (lug'atlarning asosiy qismi) odatda amortizatsiyalangan vaqtda O(1) da qo'shish amalga oshiriladi, lekin "o'rtasi" tushunchasi mavjud emas.

Shuning uchun, agar ma'lumotlar tuzilmasi tartiblangan bo'lsa va massiv sifatida amalga oshirilgan bo'lsa, o'rtaga qo'shish O(n). Agar bu hash jadvali bo'lsa, qo'shish O(1), lekin "o'rtasi" tushunchasi qo'llanilmaydi.