Pythonis sõnastikus (dict) elemendi otsimine on tavaliselt amortiseeritud ajakompleksusega O(1), mis tähendab, et see on konstantne. Seda saavutatakse kasutades hajutustabelit.

Kuid harvadel juhtudel, näiteks kui on palju kokkupõrkeid või kui hash-funktsioon jagab võtmeid halvasti, võib keerukus halveneda kuni O(n), kus n on sõnastikus olevate elementide arv.

Seega ei ole otsing alati rangelt O(1), kuid praktikas ja enamikul juhtudel on see just selline.

Eelmine Edasi