Обозначение Big Oh и вычисление времени выполнения для тройного вложенного цикла

Question

В области компьютерных наук очень важно, чтобы специалисты по вычислительной технике знали, как рассчитать время работы алгоритмов для оптимизации кода. Для вас, ученых-компьютерщиков, я задаю вопрос.

Я понимаю, что в терминах n цикл с двойным вложением обычно имеет время выполнения n ² , а цикл с тройным вложением обычно имеет время выполнения n ³ .

Однако для случая, когда код выглядит так, будет ли время выполнения n4?

x = 0;
for(a = 0; a < n; a++)
    for(b = 0; b < 2a; b++)
        for (c=0; c < b*b; c++)
            x++;

Я упростил время выполнения для каждой строки, чтобы она была практически (n + 1) для первого цикла, (2n + 1) для второго цикла и (2n) ² + 1 для третьего цикла петля. Предполагая, что члены умножены вместе, и мы извлекаем наибольший член, чтобы найти Большое О, будет ли время выполнения n ⁴ , или оно все равно будет следовать за обычным временем выполнения n ³

Буду признателен за любой вклад. Заранее большое спасибо.

Answer 1

Вы правы, n * 2n * 4n ² = O (n ⁴ ).

Тройной вложенный цикл означает только то, что будет умножено три числа для определения окончательного значения Big O - каждый сам множитель зависит от того, сколько «обрабатывает» каждый цикл.

В вашем случае первый цикл выполняет O (n) операций, второй O (2n) = O (n), а внутренний цикл выполняет O (n ² ) операций, поэтому в целом O ( n * n * n ² ) = O (n ⁴ ).

Answer 2

Формально, используя сигма-нотацию, вы можете получить это:

Answer 3

Может ли это быть вопросом для Математика ?

Мои инстинктивные чувства, как у BrokenGlass, это то, что это O (n⁴).

РЕДАКТИРОВАТЬ: Сумма квадратов и Сумма кубов дают довольно хорошее понимание того, что происходит. Ответом является громкое O (n ^ 4): сумма (от a = 0 до n) of (сумма (от b = 0 до 2a) of (b ^ 2)). Внутренняя сумма совпадает с ^ 3. Поэтому ваша внешняя сумма соответствует n ^ 4.

Жаль, я подумал, что ты мог бы получить немного журналов вместо n ^ 4. Неважно.