DjangoBB LoFi version

Полная версия: Как получить итоговую сложность алгоритма?

Начало » Python для новичков » Как получить итоговую сложность алгоритма?

zlodiak

Фев. 16, 2019 14:22:14

Помогите пожалуйста разобраться. Есть код:

 #!/usr/bin/env python3
def func(data):
    copy = list(data)                # O(N)
    copy.sort()                      # O(N Log N)
    for i in range(len(data) - 1):   # O(N) 
        if copy[i] == copy[i+1]:     # O(1)
            return False             # O(1) 
    return True                      # O(1)    
func([1, 2, 3, 4 ,5])

Как пишут в учебнике, его итоговая сложность O(N Log N). Но мне это не понятно, ведь нужно сложить сложности каждой из строк:
O(N) + O(N Log N) + O(N) + O(1) + O(1) + O(1)
Разве нет?

Я так думаю потому что например в таких конструкциях всегда сложности перемножаюся:

 for i in range(3):			# O(N)
		for j in range(3):	# O(N)

O(N) + O(N) = O(N**2)

py.user.next

Фев. 16, 2019 15:10:13

zlodiak
O(N) + O(N) = O(N**2)

N * N = N ^ 2
N + N = 2 * N

Для твоего кода цикл for:
len(data) даёт O(N)
for i in range() даёт O(N)
if даёт O(1)
return даёт O(1)

Поэтому для всего цикла получается:
(N + N) * (1 + 1) = 2 * N * 2 = 4 * N
потом 4 * N преобразуется в N

Дальше всё складывается и общее выражение упрощается по принципу:
N + N = 2 * N = N
1 + 1 = 2 = 1
N + 1 = N

O(N) + O(N Log N) + O(N) + O(1) + O(1) + O(1) = O(N Log N) + O(N) + O(1) = O(N Log N) + O(N)

Дальше во всей формуле берётся самое большое значение с N и считается временной сложностью алгоритма.

Тут виды сложностей из книжки в порядке возрастания:

от себя одна:
0) постоянная сложность: O(1)

1) логарифмическая сложность: O(log n)
2) линейная сложность: O(n)
3) квазилинейная сложность: О(n log n)
4) квадратичная cложность: O(n^2)
5) кубическая сложность: О(n^3)
6) полиномиальная сложность: О(n^p), p - натуральное
7) экспоненциальная сложность: О(2^n) , О(n^n).

Вообще, есть ещё сложности, но они редкие.

tags: complexity