нахождение временной сложности алгоритма

Question

Я пытаюсь найти большую тэту следующего кода:

k=0,x=0,y=0
for i=1 to 2n do:
    for j=0 to i^2 do:
        k+=1
    t=k
    while t>=0 do:
        ...(O(1) operations)
        t=t-0.5

Я понимаю, что первый цикл всегда выполняется при O (n), второй - не более O ((2n) ^ 2) - когда я = 2н. и что время запускает 2n ^ 2 (это правильно?)

, поэтому мой расчет: T (n) = O (n) * (O (n ^ 2) + O (n ^ 2))= O (n ^ 3)

Я не уверен, прав ли я и как мне теперь найти большую Омегу - чтобы показать, что она равна Большой O.

Answer 1

Вы можете проанализировать функцию T (N). (На данный момент я игнорирую while t>=0..., чтобы быть более ясным) Мы считаем, что основной операцией является эта: k+=1, и мы подсчитываем, сколько раз она выполняется. По математике:

T (n) =

=

=

И это полиномиальная функция, которая равна , потому что мы можем найти константы для того, чтобы функция была больше, чем n ^ 3, и найти другие на порядок меньше n ^ 3. .

Учитывая, что while t>=0 не изменит конечный результат, потому что он изменяет только постоянные факторы