Öz həllinin mürəkkəbliyi

Başqasının alqoritminin mürəkkəbliyini bilmək kifayət deyil: müsahibədə və işdə öz kodunuzu tez qiymətləndirmək lazımdır. Bunun üçün sadə qaydalar ardıcıllığı və hər şeyi korlayan «gizli» bahalı əməliyyatların siyahısı var.

Addım-addım qiymətləndirmə

1. Girişin ölçülərini müəyyən edin: n, m, k. Hamısı n deyil.
2. Koda yuxarıdan aşağı baxın və hər sətrin və ya blokun qiymətini yazın.
3. Ardıcıl bloklar toplanır, iç-içə olanlar vurulur.
4. Dövrdə gövdənin qiymətini təkrarların sayına vurun (gövdə sonrakı təkrarlarda bahalıdırsa, cəmi hesablayın).
5. Dominant həddi saxlayın, sabitləri atın.
6. Yaddaşı ayrıca sayın: girişlə nə böyüyür (surətlər, lüğətlər, rekursiya steki).

def count_pairs(a, target):         # n = len(a)
    a = sorted(a)                   # O(n log n)
    lo, hi = 0, len(a) - 1          # O(1)
    cnt = 0
    while lo < hi:                  # at most n iterations
        s = a[lo] + a[hi]           # O(1) per iteration
        if s == target:
            cnt += 1
            lo += 1
            hi -= 1
        elif s < target:
            lo += 1
        else:
            hi -= 1
    return cnt                      # total: O(n log n) + O(n) = O(n log n)

print(count_pairs([1, 2, 3, 4, 5, 6], 7))
print(count_pairs([5, 1, 5, 2, 8], 10))

3
2

Çeşidləmə O(n log n), iki göstəricili dövr O(n): cəm qaydası ilə O(n log n) qalır.

Gizli xərclər