Вложенный анализ l oop (каждый l oop ограничивает внутреннюю l oop)

Question

• В своей лекции по структуре данных я получил домашнее задание об алгоритмах и сложности времени. На самом деле я не смог найти, что мне нужно для этого сделать.

Вопрос: Какова временная сложность этого алгоритма?

• Моим решением было проанализировать l oop с помощью l oop, удалив постоянные и младшие члены каждого из l oop. По этой причине есть три петли внутри друг друга. Сложность должна быть O (n ³ ) . Критическим моментом является то, что самый внутренний l oop является , динамически ограниченным.

В чем ошибка в этой таблице (если есть) :

int c = 0;
for (int i = 0; i < n * n; ++i)
    for (int j = 0; j < n; ++j)
        for (int k = 0; k < j * 2; ++k)
            c = c + 1;
return c;

Все ответы приветствуются.

Answer 1

Чтобы вычислить сложность времени, вы можете попытаться оценить количество итераций самой внутренней l oop.

• l oop в k вычисляет простое выражение 2 * j раз.
• l oop на j работает n раз. Следовательно, внутренний l oop работает 2 * n * (n + 1) / 2, что упрощается до n * (n + 1).
• , внешний l oop выполняется n * n раз. Следовательно, внутренние циклы выполняются ровно n * n * n * (n + 1) раз.

Упрощение для доминирующего члена приводит к сложности времени: n ⁴ .

Все же очень проницательный компилятор уменьшил бы эту сложность до постоянного времени O (1) и сгенерировал бы код для:

return n * n * n * (n + 1);

Попытка сделать это на Исследователь компилятора Годболта показывает, что ни один из распространенных компиляторов не достигает этого на данный момент, хотя clang делает все возможное, чтобы оптимизировать код с помощью непостижимого кода SIMD.