Временная сложность вложенного цикла for

Быстрый способ объяснить complexity это - визуализировать.

если complexity и i, и j равны от 0 до N, легко asymptotic-complexity увидеть O (N ^ 2)

O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O

в данном o-notation случае это:

O
O O
O O O
O O O O
O O O O O
O O O O O O
O O O O O O O
O O O O O O O O

Получается 1/2 o-notation от N ^ 2, что по-прежнему asymptotic-complexity O (N ^ 2)

big-o

complexity-theory

time-complexity

2022-11-19T09:43:49+00:00