Определение временных сложностей алгоритмов наихудшего случая

Question

Имеют ли два алгоритма одинаковую тэта-характеристику Θ (n ^ 2)?

int sum = 0;
for (int i = 0; i < n; i++ )
    for (int j = 0; j < n * n; j++ )
        sum++;

int sum = 0;
for ( int i = 0; i < n; i++)
    for ( int j = 0; j < i; j++)
        sum++;

Если нет, значит ли это, что эта характеристика не Θ (n ^ 3)?

int sum = 0;
for ( int i = 0; i < n; i++)
    for ( int j = 0; j < i * i; j++ )
        for ( int k = 0; k < j; k++ )
            sum++;

Answer 1

@ Дэн, Для первого вы действительно имели в виду j < n * n, а не j < n?Если это так, временная сложность первого is (n ^ 3), не так ли?

Если вы имели в виду j < n, то я считаю, что первые два - это both (n ^ 2): Первый шаг состоит из n ^ 2 шагов, второй - 1 + 2 + ... + n = n (n + 1) / 2, что равно Θ (n ^ 2).

I 'Я думаю, что третий - Θ (n ^ 4), но это труднее доказать.Определенно O (n ^ 4).