Почему алгоритм O(n^3)?

Question

Рейтинг: -2Ответов: 1Опубликовано: 02.08.2023

def a(N):
    k = 0
    for i in range (N**2):
        for j in range (N//2):
            print(k)
            k += 1

Answer 1

▲ 6Принят

for i in range(N**2):

Итого примерно N² раз выполнить

for j in range(N//2):

нечто, что выполняется примерно N/2 раза, т.е. всего N³/2 раз сделать

print(k)
k += 1

что выполняется за константное время. Ну, а при определении O(...) все константы отбрасываются. Итак, получаем O(N³)...

Ответы