時間複雜度由小到大依次為:

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

時間複雜度 描述
O(1) 常數時間
O(logn) 對數時間
O(n) 線性時間
O(nlogn) 線性對數時間
O(n^2) 平方時間
O(n^3) 立方時間
O(2^n) 指數時間
O(n!) 階乘時間
O(n^n) 階乘時間

常見的時間複雜度

O(1)：常數時間

1
2
3
def constant_algo(items):
    result = items[0] * items[0]
    print(result)

O(n)：線性時間

1
2
3
def linear_algo(items):
    for item in items:
        print(item)

O(n^2)：平方時間

1
2
3
4
def quadratic_algo(items):
    for item in items:
        for item2 in items:
            print(item, ' ', item2)

O(logn)：對數時間

1
2
3
4
5
6
7
8
9
10
def logarithmic_algo(items):
    for index in range(1,len(items)):
        position = index
        current_value = items[index]

        while position>0 and items[position-1]>current_value:
            items[position]=items[position-1]
            position = position-1

        items[position]=current_value

O(nlogn)：線性對數時間

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
def linearithmic_algo(items):
    if len(items) > 1:
        mid = len(items) // 2
        left = items[:mid]
        right = items[mid:]

        linearithmic_algo(left)
        linearithmic_algo(right)

        i = 0
        j = 0
        k = 0

        while i < len(left) and j < len(right):
            if left[i] < right[j]:
              items[k] = left[i]
              i += 1
            else:
                items[k] = right[j]
                j += 1
            k += 1

        while i < len(left):
            items[k] = left[i]
            i += 1
            k += 1

        while j < len(right):
            items[k]=right[j]
            j += 1
            k += 1

O(2^n)：指數時間

1
2
3
4
5
6
7
8
9
def exponential_algo(items):
    if len(items)==0:
        return [[]]
    smaller = exponential_algo(items[:-1])
    extra = items[-1:]
    new = []
    for small in smaller:
        new.append(small+extra)
    return smaller+new

O(n!)：階乘時間

1
2
3
4
5
6
7
8
9
def factorial_algo(items):
    if len(items)==0:
        return [[]]
    smaller = factorial_algo(items[:-1])
    new = []
    for small in smaller:
        for i in range(0,len(small)+1):
            new.append(small[:i]+items[-1:]+small[i:])
    return smaller+new

O(n^n)：階乘時間

1
2
3
4
5
6
7
8
9
def n_power_n_algo(items):
    if len(items)==0:
        return [[]]
    smaller = n_power_n_algo(items[:-1])
    new = []
    for small in smaller:
        for i in range(0,len(small)+1):
            new.append(small[:i]+items[-1:]+small[i:])
    return smaller+new

O(n^3)：立方時間

1
2
3
4
5
def cubic_algo(items):
    for item in items:
        for item2 in items:
            for item3 in items:
                print(item, ' ', item2, ' ', item3)