Nəzəriyyə "n böyüdükcə vaxt necə artır?" sualına cavab verir, ölçmə isə konkret maşında konkret vaxtı göstərir. Yaxşı mühəndis hər ikisini birləşdirir: təhlildən gözlənti çıxarır, ölçmə ilə yoxlayır. Bu dərsdə mürəkkəbliyi eksperimentlə yoxlamaq üçün kiçik alətlər quracağıq.

Ölçmə protokolu

  1. n üçün ölçüləri seçin və hər dəfə ikiqat artırın: n, 2n, 4n, ....
  2. Giriş verilənlərini taymerdən kənarda hazırlayın.
  3. Hər ölçü üçün bir neçə dəfə təkrarlayın və minimumu götürün: ən az küylüdür.
  4. T(2n) / T(n) nisbətini və ya log-log meylini hesablayın.
  5. Nəticəni nəzəri gözləntiyə uyğunlaşdırın.
MürəkkəblikT(2n) / T(n) gözləntisilog-log meyl
O(1)≈ 10
O(log n)≈ 1 (bir az çox)≈ 0
O(n)21
O(n log n)2-dən bir az çox1-dən bir az çox
O(n^2)42
O(n^3)83
O(2^n)T(n + 1) / T(n) = 2xətt yoxdur

Benchmark funksiyası və nisbətlər

bench təkrarlardan ən yaxşısını qaytarır. ratio ölçünü ikiqat artıranda vaxtın neçə dəfə artdığını göstərir. Nəticələr maşından asılıdır, buna görə cavabı dəqiq saniyələrlə yox, aralıqla yoxlayırıq.

python
import random
from time import perf_counter