Ինչ մեթոդներով եք որոշում ալգորիթմի ժամանակային բարդությունը?

Ալգորիթմի ժամանակային բարդությունը որոշելու համար սովորաբար այն վերլուծվում է այն գործողությունների քանակի միջոցով, որոնք ալգորիթմը կատարում է մուտքային տվյալների չափի կախվածությամբ (սովորաբար նշվում է n-ով):

Հիմնական մեթոդները՝

1. Անալիտիկ մոտեցում — ուսումնասիրել ալգորիթմի կոդը և հաշվել հիմնական գործողությունների քանակը n-ի կախվածությամբ: Օրինակ, եթե կա ներսի ցիկլ, որը անցնում է n տարրերով, բարդությունը կլինի մոտավորապես O(n²):

2. "Big O" նշանագրության օգտագործում — գնահատելու համար ալգորիթմի ասիմպտոտիկ վարքագիծը, անտեսելով հաստատունները և քիչ կարևոր անդամները:

3. Փորձնական մոտեցում — չափել ալգորիթմի կատարման ժամանակը տարբեր չափերի մուտքային տվյալներով և կառուցել ժամանակի կախվածության գրաֆիկը n-ից, որպեսզի փորձնականորեն որոշվի բարդությունը:

Օրինակ՝ անալիտիկ որոշման օրինակ:

def օրինակ(arr):
    for i in range(len(arr)):
        for j in range(len(arr)):
            print(arr[i], arr[j])

Այստեղ, երկու ներսի ցիկլ n տարրերով, հետևաբար ժամանակային բարդությունը մոտավորապես O(n²) է:

Այսպիսով, ժամանակային բարդությունը որոշելու համար անհրաժեշտ է հասկանալ, թե ինչպես է գործողությունների քանակը աճում մուտքային տվյալների չափի մեծացման հետ: