Как подойти к поиску сложности Big O / Time любого алгоритма

Question

All

Я всегда сомневался, когда нужно найти сложность данного кода / алгоритма. Ex.

FOR I=1 TO N
do J=1
WHILE J*J < I
do J=J+1

Приведенный выше код имеет временную сложность Big Theta (N^(3/2)). Тем не менее, я не понимаю, как ответ получен.

Может кто-нибудь подсказать мне, как найти сложность или какой-то конкретный ресурс, который может мне помочь? В большинстве случаев я нахожу код только со сложностью N, lg N , N lg N и N^2

Answer 1

Подход всегда один и тот же: определите, сколько операций выполняется как функцию N , а затем отбросьте младшие члены и константы.

Итак, в приведенном выше примере внутренний цикл повторяется примерно sqrt (I) раз, поэтому мы имеем (приблизительно) sqrt (1) + sqrt (2) + sqrt (3) + ... В результате получается функция, член высшего порядка которой равен N ^ (3/2).