sum = 0;
for(int i = 0; i < N; i++)
for(int j = i; j >= 0; j--)
sum++;
Из того, что я понимаю, первая линия 1 операция, вторая линия (i+1) операции, третья строка (i-1) операции, а четвёртая линия n операции. Означает ли это, что время работы будет 1 + (i+1)(i-1) + n? Просто эти последние шаги меня смущают.Как рассчитать худший анализ этого алгоритма?
Чтобы проанализировать алгоритм, вы не хотите идти по очереди, спрашивая: «Сколько времени занимает эта конкретная строка?» Причина в том, что каждая строка не выполняется столько же раз. Например, самая внутренняя строка выполняется целая куча раз, по сравнению с первой строкой, которая запускается только один раз.
Чтобы проанализировать такой алгоритм, попробуйте идентифицировать некоторую величину, значение которой находится в пределах постоянного коэффициента общей продолжительности работы алгоритма. В этом случае это количество, вероятно, будет «сколько раз выполняется строка sum++?», Так как, если мы знаем это значение, мы знаем общее количество времени, потраченное двумя циклами в алгоритме. Чтобы понять это, давайте выясним, что происходит с этими циклами. На первой итерации внешнего цикла i == 0, и поэтому внутренний цикл будет выполняться ровно один раз (отсчет от 0 до 0). На второй итерации внешнего цикла i == 1 и внутренний цикл выполняются ровно дважды (сначала с j == 1, один раз с j == 0. В более общем плане, на k-й итерации внешнего цикла внутренний цикл выполняет k + 1 раз. Это означает, что общая сумма число итераций внутреннего цикла задаются
1 + 2 + 3 + ... + N
этой величина может быть показана равным
N (N + 1) N^2 + N N^2 N
--------- = ------- = --- + ---
2 2 2 2
из этих двух слагаемых, N^2/2 термина является доминирующим термином роста, и поэтому, если мы игнорируем его постоянную ctors мы получаем время выполнения O (N).
Не смотрите на этот ответ как на что-то, что вы должны запомнить - подумайте о всех шагах, необходимых для ответа. Мы начали с того, что нашли количество, чтобы подсчитать, а затем увидели, как на это количество повлияло выполнение циклов. Из этого мы смогли получить математическое выражение для этой величины, которое мы затем упростили. Наконец, мы взяли полученное выражение и определили доминирующий член, который служит большой-O для общей функции.
Это не аддитив: внутренний цикл происходит один раз для КАЖДОЙ итерации внешнего контура. Так что это O (n).
Кстати, это хороший пример того, почему мы используем асимптотические обозначения для такого рода вещей - в зависимости от определения «операции» точные детали счета могут сильно варьироваться. (Как, sum++ одна операция, или это add sum to 1 giving temp; load temp to sum?) Но так как мы знаем, что все, что может быть скрыто в постоянном коэффициенте, все равно будет O (n).
Нет; вы не учитываете определенное количество операций для каждой строки, а затем добавляете их. Вся конструкция таких конструкций, как «for», позволяет использовать одну или несколько строк кода. Вы должны использовать навыки мышления и логики, чтобы выяснить, сколько раз будет выполняться строка «sum ++», как функция N. Hint: она запускается раз в каждый раз, когда встречается третья строка.
Сколько раз встречалась вторая линия?
Каждый раз, когда встречается вторая строка, устанавливается значение 'i'. Сколько раз в третьей строке выполняется с этим значением i? Поэтому, сколько раз он будет работать в целом? (Подсказка: если я дам вам другую сумму денег в нескольких разных случаях, как вы узнаете, сколько всего я вам дал?)
Каждый раз, когда встречается третья строка, четвертая строка происходит один раз.
Какая линия чаще всего встречается? Как часто это происходит, с точки зрения N?
Работа из наизнанку.
sum++
Это отдельная операция на ее собственной, так как она не повторяется.
for(int j = i; j >= 0; j--)
Это петли i + 1 раз. Есть несколько операций, но вы, вероятно, не имеете в виду количество инструкций asm. Поэтому я возьму на себя этот вопрос, это множитель i + 1. Поскольку содержимое цикла является одной операцией, цикл и его блок выполняют операции i + 1.
for(int i = 0; i < N; i++)
Это петли N раз. Таким образом, как и раньше, это множитель N. Поскольку блок выполняет операции i + 1, этот цикл выполняет всего N (N + 1)/2 операций. И это ваш ответ! Если вы хотите рассмотреть сложность большого О, то это упрощает до O (N).
Так что догадайтесь, какой интерес вы представляют собой сумму ++ и сколько раз вы ее выполняете.
Окончательный стат суммы даст вам этот ответ.
На самом деле ваш цикл просто:
Sigma (п) п идет от 1 до N.
Который равен: N*(N+1)/2 Это даст вам в биг-о-нотации O(N^2)
Также рядом имя вашего вопроса, в вашем алгоритме нет худшего случая. Или вы могли бы сказать, что худший случай - когда N идет в бесконечность.
Использование Sigma нотации для представления ваших петель:
Вам нужно вычислить сложность по отношению к N, а не к счетчикам цикла. – thkala