Ի՞նչ է ժամանակային բարդությունը նոր տարր ավելացնելու համար բառարանում։

Նոր տարր ավելացնելու ժամանակային բարդությունը բառարանի մեջ (օրինակ, Swift-ի Dictionary կամ Objective-C-ի NSMutableDictionary) սովորաբար կազմում է O(1) միջինում: Դա պայմանավորված է նրանով, որ բառարանը իրականացվում է հեշ-թերթի հիման վրա, որտեղ հեշի հաշվարկը և տեղադրումը կատարվում են հաստատուն ժամանակում:

Սակայն, ամենավատ դեպքերում, բախումների կամ ներքին զանգվածի ընդլայնման անհրաժեշտության դեպքում, բարդությունը ժամանակավորապես կարող է աճել մինչև O(n), որտեղ n տարրերի քանակն է:

Swift-ում օրինակ:

var dict = [String: Int]()
dict["key"] = 42 // Միջինում ավելացում O(1)