Python-da sözlükdən açar ilə dəyər almağın algoritmik mürəkkəbliyi nədir?

Python-da lüğətdən açar üzrə dəyəri almağın algoritmik mürəkkəbliyi orta hesabla O(1)-dir.

Bu, hash cədvəllərindən istifadə etməklə mümkündür. Açar hash-lənir və əldə edilən hash, müvafiq dəyərin saxlanıldığı cədvəldə indeks (kova) müəyyən etmək üçün istifadə olunur. İdeal halda (hash toqquşmaları olmadan), bu kovaya giriş sabit vaxt alır.

Ən pis halda, çox sayda hash toqquşması olarsa, mürəkkəblik O(n)-ə çatdıra bilər; burada n, lüğətdəki elementlərin sayıdır. Bu, bütün açarların eyni kovaya hash-ləndiyi zaman baş verir və lazım olan dəyəri tapmaq üçün həmin kovadakı bütün elementləri ardıcıl şəkildə yoxlamaq lazımdır. Lakin, Python-un standart lüğət tətbiqi toqquşma həll etmə və rehash mexanizmlərindən istifadə edir ki, bu da belə bir ssenarinin ehtimalını minimuma endirir.

# Açar üzrə dəyəri alırıq
value = my_dict[key]