Я знаю, что большая сложность этого алгоритма O(n^2), но я не могу понять, почему.
int sum = 0;
int i = 1; j = n * n;
while (i++ < j--)
sum++;
Даже если мы устанавливаем j = n * n в начале, мы увеличиваем я и уменьшаем j на каждой итерации, поэтому не должно быть результирующего числа итераций намного меньше, чем n*n?
На каждой итерации вы увеличиваете i и декремент j, что эквивалентно простому увеличению i на 2. Поэтому общее число итераций равно n ^ 2/2, и это все еще O (n ^ 2).
сложность big-O игнорирует коэффициенты. Например: O(n), O(2n) и O(1000n) - все те же O(n). Аналогично, O(n^2) и O(0.5n^2) - это время O(n^2).
В вашей ситуации вы по существу увеличиваете счетчик циклов на 2 каждый раз через свой цикл (поскольку j-- имеет тот же эффект, что и i++). Таким образом, ваше время работы O(0.5n^2), но то же, что и O(n^2) при удалении коэффициента.
У вас будет ровно n*n/2 итераций цикла (или (n*n-1)/2, если n нечетно).
В большой записи O мы имеем O((n*n-1)/2) = O(n*n/2) = O(n*n), потому что постоянные факторы "не учитываются".
Ваш алгоритм эквивалентен
while (i += 2 < n*n)
...
который равен O(n^2/2), который совпадает с O(n^2), потому что большая сложность O не заботится о константах.
Пусть m - количество принятых итераций. Тогда,
i + m = n ^ 2 - m
что дает,
m = (n ^ 2-i)/2
В записи Big-O это означает сложность O (n ^ 2).
Да, этот алгоритм O (n ^ 2).
Чтобы вычислить сложность, у нас есть таблица сложности:
О (1)
O (log n)
На)
O (n log n)
O (N²)
О (п ^ а)
О (а ^ п)
O (п!)
Каждая строка представляет собой набор алгоритмов. Набор алгоритмов, который находится в O (1), тоже находится в O (n) и O (n ^ 2) и т.д. Но не в обратном порядке. Итак, ваш алгоритм реализует предложения n * n/2.
O (n) O (nlogn) O (n * n/2) O (N²)
Таким образом, набор алгоритмов, которые включают сложность вашего алгоритма, равен O (n²), поскольку O (n) и O (nlogn) меньше.
Например: Для n = 100 сумма = 5000. = > 100 O (n) 200o (n & bull; logn) 5000 (n * n/2) 10000 (п ^ 2)
Прошу прощения за мой английский.
Несмотря на то, что мы начинаем j = n * n в начале, мы увеличиваем я и уменьшаем j на каждой итерации, поэтому не должно быть результирующего числа итераций намного меньше n * n?
Да! Вот почему O (n ^ 2). По той же логике она намного меньше n * n * n, что делает ее O (n ^ 3). Это даже O (6 ^ n), по аналогичной логике.
big-O дает вам информацию о верхних границах.
Я считаю, что вы пытаетесь спросить, почему сложность - это theta (n) или omega (n), но если вы просто пытаетесь понять, что такое big-O, вам нужно действительно понять, что он дает верхние границы для функций в первую очередь.