Чӣ тавр арзёбӣ кардани мураккабии вақти амалиёти ворид кардан, хориҷ кардан ва ҷустуҷӯ кардани унсурҳо дар рӯйхати пайваст?

Вақтли мураккабликлар боғланган рўйхатда амалларнинг аниқ нима қилишимизга ва керакли элементга киришимизга боғлиқ:

• Қўшиш:

  • Рўйхат бошига — O(1), чунки ҳаволаларни ўзгартириш етарли.
  • Бир йўналишли боғланган рўйхатнинг охирига — O(n), тўлиқ рўйхатни ўтказиш керак.
  • Оҳирига кўрсаткич билан — O(1).
  • Ҳар қандай жойга (индекс ёки қиймат бўйича) — O(n), позицияни топиш керак.

• Ўчириш:

  • Биринчи элементни ўчириш — O(1).
  • Қиймат ёки индекс бўйича ўчириш — O(n), элемент ва унинг олдингисини топиш керак.

• Қидириш:

  • Қиймат бўйича элементни қидириш — O(n), рўйхатни ўтказиш керак.

Шу тариқа, асосий амалиётлар керакли узелга тўғридан-тўғри кириш йўқ бўлса, чизиқли вақт талаб қилади. Бу боғланган рўйхатларнинг давомий табиати билан боғлиқ.