Я не понимаю, как 2-й цикл имеет O (я ^ 2)?

Question

второй цикл выполняется от i до i ^ 2 -1, поэтому нет.раз = i ^ 2 - i + 1

function(int n) {

внешние пробеги n раз

    for (int i = 0; i < n; i++) {
        for (int j = i; j < i * i; j++) {
            if (j % i == 0) {

это работает j раз

                for (int k = 0; k < j; k++) {
                    printf("*");
                }
            }
        }
    }
}

Answer 1

так что нет.времен = i ^ 2 - i + 1

Если i становится больше , например, чрезвычайно большим, то оба значения i^2 amd i становятся чрезвычайнобольшой.Однако i^2 увеличивается быстрее , чем i, тогда увеличение i можно игнорировать по сравнению с увеличением i^2.Для записи Big-O из сложности времени это выражается как O (i ^ 2) .

Кроме того, это "O "(буква O), а не" 0 "(число ноль).

Answer 2

Вы говорите, что поскольку внутренний цикл переходит от i к i², сложность не должна быть O (i²).
Сложность действительно не более O (i²), но:

1. Для i = 1 2-й цикл выполняется 1 раз
2. Для i = 10 , 90 раз (не слишком далеко от 100)
3. Для i = 100 , 9900 раз (не слишком далеко от 10000)
4. Для i = 1000 , 999000 раз (не слишком далеко)от 1M)

Каждый раз, когда вы умножаете i на число n (в моем случае 10), внутренний цикл будет выполняться чуть больше, чем n² больше раз.Это показывает, что сложность составляет по крайней мере O (i²).

Вывод: сложность составляет точно (= максимум + по крайней мере) O (i²)

---

Общие знания о сложности:

Большая часть кода, который вы когда-либо увидите, имеет сложность в нижеуказанном упорядоченном списке или их комбинацию (подробнее об этомпозже):
n^0 (= constant) < log2(n) < sqrt(n) < n < n^2 < exp(n)

Сложность - это термин, который применяется только для очень больших чисел.
Он не имеет значения для небольших значений, как вы увидите, например, здесь ,

В вашем случае, с очень большим значением, i² подавляет перед i, поэтому O(i²-i) = O(i²).

В общем, сложность только умножается:

• Ваш внешний цикл равен O(n)
• Ваш внутренний цикл равен O(n^2)
• Результат: пример кода: O(n^3)

ОчевидноКогда вы комбинируете сложности, порядок останется неизменным.
Например, мой ранее упорядоченный список, умноженный на O(n), станет:
n < n*log2(n) < n*sqrt(n) < n^2 < n^3 < n*exp(n)

Как видите, благодаряв моем предыдущем списке были значения между n и n ^ 2.

Answer 3

Вы найдете ответ здесь

for (int j = i; j < i * i; j++) {

j работает на i ^ 2 (или i * i), что приводит к O (i ^ 2) для внутреннего цикла