Большая O-нотация для алгоритма
Я занят выполнением задания и борюсь с вопросом. Я знаю, что не должен задавать прямые вопросы о заданиях, поэтому я понимаю, что не получаю прямых ответов. Но здесь все равно идет.
Мы должны вычислить сложность выполнения различных алгоритмов, один из которых я застрял в следующем.
for(int i = 1 ; i < n ; i++)
for(int j = 0 ; j < i ; j +=2)
sum++;
Теперь, с моим пониманием, моя первая мысль будет меньше, чем O (n2), потому что вложенный цикл не выполняется полные n раз, и, тем не менее, переменная j увеличивается на 2 каждый цикл, а не выполняет итерацию, как нормальный цикл for. Хотя, когда я выполнял некоторые симуляции кода с N = 10, N = 100, N = 1000 и т. Д., Я получил следующие результаты, когда вывел переменную суммы.
N = 10 : 25,
N = 100 : 2500,
N = 1000 : 250000,
N = 10000 : 25000000
Когда я смотрю на эти результаты, обозначения O кажутся такими, что они должны быть намного больше, чем просто O (n).
4 варианта, которые нам были даны в задании: O (1), O (n2), O (n) и O (logn). Как я уже говорил ранее, я не могу понять, насколько он может быть таким большим, как O (n2), но результаты указывают на это. Так что я просто думаю, что не до конца понимаю, или мне не хватает какой-то ссылки.
Любая помощь будет оценена!
Решение
Обозначение Big O не дает вам количество операций. Это просто говорит вам, как быстро он будет расти с ростом ввода. И это то, что вы наблюдаете.
Когда вы увеличили ввод c раз, общее количество операций растет c^2,
Если бы вы точно рассчитали (почти) точное количество операций, вы бы получили (n^2)/4,
Конечно, вы можете рассчитать его с помощью сумм, но, поскольку я не знаю, как использовать математику в SO, я дам «эмпирическое» объяснение. Простой цикл внутри цикла с одинаковыми начальными и конечными условиями дает n^2, Такой цикл создает матрицу всех возможных комбинаций для "i" а также "j", Так что если начало 1 и конец N в обоих случаях вы получаете N*N комбинации (или итерации эффективно).
Тем не менее, ваш внутренний цикл предназначен для i < j, Это в основном делает треугольник из этого квадрата, то есть 1-й 0.5 фактор, а затем вы пропустите любой другой элемент, это еще один 0.5 фактор; умножить вы получите 1/4.
А также O(0.25 * n^2) = O(n^2), Иногда людям нравится оставлять этот фактор, потому что он позволяет сравнивать два алгоритма с одинаковой сложностью. Но это не меняет соотношение роста по отношению к n,
Другие решения
Имейте в виду, что Big-O асимптотический нотации. Константы (аддитивные или мультипликативные) имеют нулевой удар в теме.
Итак, внешний цикл работает n раз, и на iвремя работает внутренний цикл i / 2 раз. Если бы не / 2 часть, это будет сумма всех чисел 1 .. n, который хорошо известен n * (n + 1) / 2, Это расширяется до a * n^2 + b * n + c для ненулевого a, так что это O(n^2),
Вместо суммирования n числа, мы суммируем n / 2 номера. Но это все еще где-то вокруг (n/2) * ((n/2) + 1) / 2, Который все еще расширяется до d * n^2 + e * n + f для ненулевого dтак еще O(n^2),
Из вашего вывода это выглядит так:
сумма ~ = (п ^ 2) / 4.
Это, очевидно, O (n ^ 2) (на самом деле вы можете заменить O на тета).
Вы должны вспомнить определение для обозначения Big-O. Увидеть http://en.wikipedia.org/wiki/Big_O_notation.
Дело в том, что количество операций здесь зависимый на площади nдаже если общее число меньше n². Тем не менее, пересчет это то, что имеет значение для записи Big-O, таким образом, это O(n²)
С:
for (int i = 1 ; i < n ; i++)
for (int j = 0 ; j < i ; j +=2)
sum++;
У нас есть:
0+2+4+6+...+2N == 2 * (0+1+2+3+...+N) == 2 * (N * (N+1) / 2) == N * (N+1)
так, с n == 2N, у нас есть (n / 2) * (n / 2 + 1) ~ = (n * n) / 4
так O(n²)
Ваше понимание в отношении сложности времени не подходит. Сложность времени — это не только вопрос переменной ‘sum’. Sum ‘только вычисляет, сколько раз внутренний цикл повторяется, но вы также должны учитывать общее количество итераций внешнего цикла.
Теперь рассмотрим вашу программу:
for(int i = 1 ; i < n ; i++)
for(int j = 0 ; j < i ; j +=2)
sum++;
Временная сложность означает время выполнения вашей программы по отношению к входным значениям (здесь n). Здесь время выполнения не означает фактического времени, необходимого для выполнения вашей программы на вашем компьютере. Фактическое требуемое время варьируется от машины к машине. Поэтому, чтобы получить независимость от машины время выполнения, обозначение Big O очень полезно. Бог O на самом деле происходит из математики и описывает время выполнения в терминах математических функций.
Внешний цикл выполняется всего (n-1) раз. Для каждого из этих (n-1) значений (начиная с i = 1) внутренний цикл повторяется i / 2 раза. Поэтому общее количество итераций внутреннего цикла = 1 + 1 + 2 + 2 + 3 + 3 + … (п / 2) + (N / 2) = 2 (1 + 2 + 3 + … + п / 2) = 2 * (п / 2 ( N / 2 + 1)) / 2 = п ^ 2/4 + п / 2.
аналогично ‘sum ++’ также выполнено всего n ^ 2/4 + n / 2 раза. Теперь рассмотрим стоимость строки 1 программы = c1, стоимость строки 2 = c2 и стоимость строки 3 = c3. Эти приведения могут быть разными для другая машина. поэтому общее время, необходимое для выполнения программы = c1 * (n-1) + c2 * (n ^ 2/4 + n / 2) + c3 * (n ^ 2/4 + n / 2) = (c2 + c3) n ^ 2/4 + (c2 + c3) n / 2 + c1 * n-c1. Таким образом, требуемое время может быть выражено в терминах математической функции. В обозначении Big O можно сказать, что это O ((c2 + c3) n ^ 2/4 + (c2 + c3) n / 2 + c1 * n-c1). В случае обозначения Big O члены младшего порядка и коэффициент члена высшего порядка можно игнорировать. потому что для большого значения n, n ^ 2 намного больше, чем n. так что вы можете сказать, что это O ((c1 + c2) n ^ 2/4). Также как и для любого значения n, n ^ 2 больше, чем (c1 + c2) n ^ 2/4 на постоянный коэффициент, поэтому Вы можете сказать, что это O (n ^ 2).