Большой О, как ты это вычисляешь / приближаешь?

Question

Большинство людей, имеющих высшее образование в области CS, наверняка знают, что Большая буква " О " означает.Это помогает нам измерить, насколько (в) эффективен алгоритм на самом деле, и знаете ли вы, в к какой категории относится проблема, которую вы пытаетесь решить вы можете выяснить, возможно ли все еще выжать из себя эту небольшую дополнительную производительность.¹

Но мне любопытно, как это сделать ты вычислить или приблизить сложность ваших алгоритмов?

¹ _{но, как говорится, не переусердствуйте, преждевременная оптимизация - корень всего зла, и оптимизация без обоснованной причины также должна заслуживать этого названия.}

Answer 1

Я сделаю все возможное, чтобы объяснить это здесь простыми словами, но имейте в виду, что моим студентам требуется пара месяцев, чтобы окончательно усвоить эту тему.Вы можете найти более подробную информацию в главе 2 настоящего руководства. Структуры данных и алгоритмы на Java книга.

---

Там нет никакого механическая процедура это можно использовать для получения большого количества денег.

В качестве "кулинарной книги", чтобы получить Большой ох из фрагмента кода вам сначала нужно понять, что вы создаете математическую формулу для подсчета количества шагов вычислений, выполняемых при вводе некоторого размера.

Цель проста:сравнивать алгоритмы с теоретической точки зрения, без необходимости выполнения кода.Чем меньше количество шагов, тем быстрее работает алгоритм.

Например, допустим, у вас есть этот фрагмент кода:

int sum(int* data, int N) {
    int result = 0;               // 1

    for (int i = 0; i < N; i++) { // 2
        result += data[i];        // 3
    }

    return result;                // 4
}

Эта функция возвращает сумму всех элементов массива, и мы хотим создать формулу для подсчета вычислительная сложность этой функции:

Number_Of_Steps = f(N)

Итак, у нас есть f(N), функция для подсчета количества вычислительных шагов.Входными данными функции являются размеры обрабатываемой структуры.Это означает, что эта функция вызывается следующим образом:

Number_Of_Steps = f(data.length)

Параметр N берет на себя data.length ценность.Теперь нам нужно фактическое определение функции f().Это делается из исходного кода, в котором каждая интересная строка пронумерована от 1 до 4.

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

Мы собираемся добавить индивидуальное количество шагов функции, и ни объявление локальной переменной, ни оператор return не зависят от размера функции. data массив.

Это означает, что строки 1 и 4 занимают C шагов каждая, и функция выглядит примерно так:

f(N) = C + ??? + C

Следующая часть состоит в том, чтобы определить значение for заявление.Помните, что мы подсчитываем количество вычислительных шагов, а это означает, что тело for оператор будет выполнен N времена.Это то же самое, что добавить C, N времена:

f(N) = C + (C + C + ... + C) + C = C + N * C + C

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

Чтобы получить настоящий BigOh, нам нужно Асимптотический анализ функции.Примерно это делается следующим образом:

1. Уберите все константы C.
2. От f() получить полиномиум в своем standard form.
3. Разделите члены полинома и отсортируйте их по скорости роста.
4. Оставь себе ту, которая становится больше, когда N подходы infinity.

Наш f() имеет два термина:

f(N) = 2 * C * N ^ 0 + 1 * C * N ^ 1

Забирая все C константы и избыточные части:

f(N) = 1 + N ^ 1

Поскольку последний член - это тот, который становится больше, когда f() приближается к бесконечности (подумайте о пределы) это главный аргумент, и sum() функция имеет большое значение:

O(N)

---

Есть несколько приемов для решения некоторых сложных задач:использование суммирование когда сможешь.

В качестве примера, этот код может быть легко решен с помощью суммирования:

for (i = 0; i < 2*n; i += 2) {  // 1
    for (j=n; j > i; j--) {     // 2
        foo();                  // 3
    }
}

Первое, о чем вас нужно было спросить, - это порядок выполнения foo().В то время как обычным должно быть O(1), вам нужно спросить об этом своих профессоров. O(1) означает (почти, в основном) постоянную C, независимо от размера N.

Тот Самый for утверждение о предложении номер один является сложным.В то время как индекс заканчивается на 2 * N, увеличение производится на два.Это означает, что первый for выполняется только N шаги, и нам нужно разделить количество на два.

f(N) = Summation(i from 1 to 2 * N / 2)( ... ) = 
     = Summation(i from 1 to N)( ... )

Номер предложения два это еще сложнее, поскольку зависит от значения i.Взгляните:индекс i принимает значения:0, 2, 4, 6, 8, ..., 2 * N, и второй for быть казненным:N раз больше первого, N - 2 раза больше второго, N - 4 раза больше третьего...до этапа N/2, на котором выполняется второй for никогда не будет казнен.

По формуле это означает:

f(N) = Summation(i from 1 to N)( Summation(j = ???)(  ) )

Опять же, мы ведем подсчет количество шагов.И по определению, каждое суммирование всегда должно начинаться с единицы и заканчиваться числом, большим или равным единице.

f(N) = Summation(i from 1 to N)( Summation(j = 1 to (N - (i - 1) * 2)( C ) )

(Мы предполагаем, что foo() является O(1) и берет C шаги.)

У нас здесь проблема:когда i принимает значение N / 2 + 1 в дальнейшем внутреннее Суммирование заканчивается отрицательным числом!Это невозможно и неправильно.Нам нужно разделить суммирование на две части, что является ключевым моментом в данный момент i принимает N / 2 + 1.

f(N) = Summation(i from 1 to N / 2)( Summation(j = 1 to (N - (i - 1) * 2)) * ( C ) ) + Summation(i from 1 to N / 2) * ( C )

С момента переломного момента i > N / 2, внутренний for не будет выполнен, и мы предполагаем постоянную сложность выполнения C в его теле.

Теперь суммирование можно упростить, используя некоторые правила идентификации:

1. Суммирование (w от 1 до N) ( C ) = N * C
2. Суммирование (w от 1 до N) (A (+/-) B) = Суммирование (w от 1 до N) (A) (+/-) Суммирование (w от 1 до N) ( B)
3. Суммирование (w от 1 до N) (w * C) = C * Суммирование (w от 1 до N)(w) (C - константа, не зависящая от w)
4. Суммирование (w от 1 до N) (w ) = (N * (N + 1)) / 2

Применение некоторой алгебры:

f(N) = Summation(i from 1 to N / 2)( (N - (i - 1) * 2) * ( C ) ) + (N / 2)( C )

f(N) = C * Summation(i from 1 to N / 2)( (N - (i - 1) * 2)) + (N / 2)( C )

f(N) = C * (Summation(i from 1 to N / 2)( N ) - Summation(i from 1 to N / 2)( (i - 1) * 2)) + (N / 2)( C )

f(N) = C * (( N ^ 2 / 2 ) - 2 * Summation(i from 1 to N / 2)( i - 1 )) + (N / 2)( C )

=> Summation(i from 1 to N / 2)( i - 1 ) = Summation(i from 1 to N / 2 - 1)( i )

f(N) = C * (( N ^ 2 / 2 ) - 2 * Summation(i from 1 to N / 2 - 1)( i )) + (N / 2)( C )

f(N) = C * (( N ^ 2 / 2 ) - 2 * ( (N / 2 - 1) * (N / 2 - 1 + 1) / 2) ) + (N / 2)( C )

=> (N / 2 - 1) * (N / 2 - 1 + 1) / 2 = 

   (N / 2 - 1) * (N / 2) / 2 = 

   ((N ^ 2 / 4) - (N / 2)) / 2 = 

   (N ^ 2 / 8) - (N / 4)

f(N) = C * (( N ^ 2 / 2 ) - 2 * ( (N ^ 2 / 8) - (N / 4) )) + (N / 2)( C )

f(N) = C * (( N ^ 2 / 2 ) - ( (N ^ 2 / 4) - (N / 2) )) + (N / 2)( C )

f(N) = C * (( N ^ 2 / 2 ) - (N ^ 2 / 4) + (N / 2)) + (N / 2)( C )

f(N) = C * ( N ^ 2 / 4 ) + C * (N / 2) + C * (N / 2)

f(N) = C * ( N ^ 2 / 4 ) + 2 * C * (N / 2)

f(N) = C * ( N ^ 2 / 4 ) + C * N

f(N) = C * 1/4 * N ^ 2 + C * N

И большой вопрос в том, что:

O(N²)

Answer 2

Большое O дает верхнюю границу временной сложности алгоритма.Обычно он используется в сочетании с обработкой наборов данных (списков), но может быть использован и в других местах.

Вот несколько примеров того, как это используется в коде на языке Си.

Допустим, у нас есть массив из n элементов

int array[n];

Если бы мы хотели получить доступ к первому элементу массива, это было бы O (1), поскольку не имеет значения, насколько велик массив, для получения первого элемента всегда требуется одно и то же постоянное время.

x = array[0];

Если бы мы хотели найти номер в списке:

for(int i = 0; i < n; i++){
    if(array[i] == numToFind){ return i; }
}

Это было бы O (n), поскольку в лучшем случае нам пришлось бы просмотреть весь список, чтобы найти наш номер.Big-O по-прежнему является O (n), хотя мы могли бы найти наш номер с первой попытки и выполнить цикл один раз, потому что Big-O описывает верхнюю границу для алгоритма (omega - для нижней границы, а theta - для жесткой границы).

Когда мы доберемся до вложенных циклов:

for(int i = 0; i < n; i++){
    for(int j = i; j < n; j++){
        array[j] += 2;
    }
}

Это O (n ^ 2), поскольку для каждого прохода внешнего цикла ( O (n)) мы должны снова просмотреть весь список, чтобы n умножилось, оставив нас с n в квадрате.

Это едва касается поверхности, но когда вы приступаете к анализу более сложных алгоритмов, в игру вступает сложная математика, включающая доказательства.Надеюсь, это хотя бы познакомит вас с основами.

Answer 3

Хотя знание того, как вычислить время "Большого О" для вашей конкретной задачи, полезно, знание некоторых общих случаев может значительно помочь вам принимать решения в вашем алгоритме.

Вот некоторые из наиболее распространенных случаев, поднятых из http://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions:

O (1) - Определение того, является ли число четным или нечетным.;использование справочной таблицы постоянного размера или хэш-таблицы

O(logn) - Поиск элемента в отсортированном массиве с помощью двоичного поиска

O(n) - Поиск элемента в несортированном списке;сложение двух n-значных чисел

O(n²) - Умножение двух n-значных чисел с помощью простого алгоритма;сложение двух матриц n × n;сортировка пузырьками или вставкой

O(n³) - Умножение двух матриц n × n с помощью простого алгоритма

O(cⁿ) - Нахождение (точного) решения задачи коммивояжера с помощью динамического программирования;определение того, эквивалентны ли два логических утверждения, с использованием грубой силы

O(n!) - Решение проблемы коммивояжера с помощью поиска методом перебора

O(nⁿ) - Часто используется вместо O (n!) для вывода более простых формул для определения асимптотической сложности

Answer 4

Маленькое напоминание:тот самый big O обозначение используется для обозначения асимптотический сложность (то есть когда размер проблемы растет до бесконечности), и он скрывает константу.

Это означает, что между алгоритмом в O (n) и алгоритмом в O (n²), самый быстрый не всегда является первым (хотя всегда существует значение n такое, что для задач размера >n первый алгоритм является самым быстрым).

Обратите внимание, что скрытая константа очень сильно зависит от реализации!

Кроме того, в некоторых случаях среда выполнения не является детерминированной функцией размер n входных данных.Возьмем, к примеру, сортировку с помощью быстрой сортировки:время, необходимое для сортировки массива из n элементов, не является постоянной величиной, а зависит от начальной конфигурации массива.

Существуют разные временные сложности:

• Наихудший случай (обычно самый простой для понимания, хотя и не всегда очень значимый)

• Средний случай (обычно гораздо сложнее разобраться ...)

• ...

Хорошим введением является Введение в анализ алгоритмов автор R.Седжвик и П.Флайолет.

Как ты говоришь, premature optimisation is the root of all evil, и (если возможно) профилирование действительно, его всегда следует использовать при оптимизации кода.Это даже может помочь вам определить сложность ваших алгоритмов.

Answer 5

Видя ответы здесь, я думаю, мы можем сделать вывод, что большинство из нас действительно приближают порядок выполнения алгоритма следующим образом глядя посмотрите на это и используйте здравый смысл вместо того, чтобы вычислять это, например, с помощью основной метод как о нас думали в университете.С учетом сказанного я должен добавить, что даже профессор поощрял нас (позже) на самом деле подумай думать об этом, а не просто вычислять.

Также я хотел бы добавить, как это делается для рекурсивные функции:

предположим, у нас есть функция типа (код схемы):

(define (fac n)
    (if (= n 0)
        1
            (* n (fac (- n 1)))))

который рекурсивно вычисляет факториал данного числа.

Первый шаг - попытаться определить эксплуатационные характеристики для только тело функции в этом случае в теле не делается ничего особенного, просто выполняется умножение (или возврат значения 1).

Таким образом, эффективность для организма - это:O(1) (постоянный).

Далее попробуйте определить это для количество рекурсивных вызовов.В этом случае мы имеем n-1 рекурсивный вызов.

Таким образом, производительность для рекурсивных вызовов равна:O(n-1) (порядок равен n, так как мы выбрасываем незначительные части).

Затем соедините эти два элемента вместе, и тогда у вас будет производительность для всей рекурсивной функции:

1 * (n-1) = O (n)

---

Питер, чтобы ответить поднятые вами вопросы; метод, который я описываю здесь, на самом деле справляется с этим довольно хорошо.Но имейте в виду, что это все еще аппроксимация и не полный математически правильный ответ.Описанный здесь метод также является одним из методов, которым нас учили в университете, и, если я правильно помню, использовался для гораздо более продвинутых алгоритмов, чем факториал, который я использовал в этом примере.
Конечно, все зависит от того, насколько хорошо вы можете оценить время выполнения тела функции и количество рекурсивных вызовов, но это так же верно и для других методов.

Answer 6

Если ваша стоимость является полиномом, просто сохраните член высшего порядка без его множителя.Например.:

O((n/2 + 1)*(n/2)) = O (n²/4 + n/2) = O (n²/4) = O(n²)

Имейте в виду, это не работает для бесконечных серий.Единого рецепта для общего случая не существует, хотя для некоторых общих случаев применимы следующие неравенства:

O(журнал регистрации N) < O(N) < O(N журнал регистрации N) < O(N²) < O(N^k) < O(eⁿ) < O(n!)

Answer 7

Я думаю об этом с точки зрения информации.Любая задача состоит в запоминании определенного количества битов.

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

Например, an if оператор, имеющий две ветви, обе с равной вероятностью, имеет энтропию 1/2 * log(2/1) + 1/2 * log(2/1) = 1/2 * 1 + 1/2 * 1 = 1.Таким образом, его энтропия равна 1 биту.

Предположим, вы ищете таблицу из N элементов, например N = 1024.Это 10-битная проблема, потому что log (1024) = 10 бит.Таким образом, если вы можете выполнить поиск по утверждениям IF, которые имеют равновероятные результаты, то должно быть принято 10 решений.

Это то, что вы получаете с помощью двоичного поиска.

Предположим, вы выполняете линейный поиск.Вы смотрите на первый элемент и спрашиваете, тот ли это, который вам нужен.Вероятности равны 1/1024, что это так, и 1023/1024, что это не так.Энтропия этого решения равна 1/1024 * log(1024/1) + 1023/1024 * log(1024/1023) = 1/1024 * 10 + 1023/1024 * около 0 = около 0,01 бита.Ты очень мало узнал!Второе решение не намного лучше.Вот почему линейный поиск выполняется так медленно.На самом деле это экспоненциально зависит от количества битов, которые вам нужно выучить.

Предположим, вы занимаетесь индексацией.Предположим, таблица предварительно отсортирована по множеству ячеек, и вы используете некоторые из всех битов в ключе для индексации непосредственно к записи таблицы.Если имеется 1024 ячейки, энтропия равна 1/1024 * log(1024) + 1/1024 * log(1024) + ...для всех 1024 возможных результатов.Это 1/1024 * 10, умноженное на 1024 результата, или 10 бит энтропии для одной операции индексации.Вот почему индексирование поиска происходит быстро.

Теперь подумайте о сортировке.У вас есть N элементов, и у вас есть список.Для каждого элемента вы должны выполнить поиск, куда этот элемент попадает в списке, а затем добавить его в список.Таким образом, сортировка занимает примерно в N раз больше шагов базового поиска.

Таким образом, сортировка, основанная на бинарных решениях, имеющих примерно равновероятные результаты, занимает около O (N log N) шагов.Алгоритм сортировки O(N) возможен, если он основан на индексирующем поиске.

Я обнаружил, что почти все проблемы с производительностью алгоритмов можно рассматривать таким образом.

Answer 8

Давайте начнем с самого начала.

Прежде всего, примите принцип, согласно которому определенные простые операции с данными могут быть выполнены в O(1) время, то есть за время, которое не зависит от размера входных данных.Эти примитивные операции в C состоят из

1. Арифметические операции (например,+ или %).
2. Логические операции (например, &&).
3. Операции сравнения (например,, <=).
4. Структурировать операции доступа (например,массив индексации, как[я], или указатель Фоль- мычание с помощью оператора ->).
5. Простое присвоение, такое как копирование значения в переменную.
6. Вызовы библиотечных функций (например, scanf, printf).

Обоснование этого принципа требует детального изучения машинных инструкций (примитивных шагов) типичного компьютера.Каждая из описанных операций может быть выполнена с помощью небольшого количества машинных команд;часто требуется только одна или две инструкции.Как следствие, несколько видов инструкций на C могут быть выполнены в O(1) время, то есть за некоторый постоянный промежуток времени, независимый от входных данных.К таким простым относятся

1. Операторы присваивания, которые не включают вызовы функций в свои выражения.
2. Читайте заявления.
3. Пишите инструкции, которые не требуют вызовов функций для оценки аргументов.
4. Операторы jump прерывают, continue, goto и возвращают выражение, где выражение не содержит вызова функции.

В C многие циклы for формируются путем инициализации индексной переменной некоторым значением и увеличения этой переменной на 1 каждый раз в цикле.Цикл for заканчивается, когда индекс достигает некоторого предела.Например, цикл for

for (i = 0; i < n-1; i++) 
{
    small = i;
    for (j = i+1; j < n; j++)
        if (A[j] < A[small])
            small = j;
    temp = A[small];
    A[small] = A[i];
    A[i] = temp;
}

использует индексную переменную i.Он увеличивает i на 1 каждый раз в цикле, и итерации останавливаются, когда i достигает n - 1.

Однако на данный момент сосредоточьтесь на простой форме for-цикла, где разница между конечным и начальным значениями, деленная на величину, на которую увеличивается индексная переменная, показывает нам, сколько раз мы обходим цикл.Это количество является точным, если только нет способов выйти из цикла с помощью оператора jump;в любом случае, это верхняя граница количества итераций.

Например, цикл for повторяет ((n − 1) − 0)/1 = n − 1 times, поскольку 0 - начальное значение i, n - 1 - это наибольшее значение, достигнутое i (т.е. когда i достигает n-1, цикл останавливается, и итерация не выполняется с i = n-1), и 1 добавляется к i на каждой итерации цикла.

В простейшем случае, когда время, проведенное в теле цикла, одинаково для каждой итерации, мы можем умножить верхнюю границу big-oh для тела на количество повторений цикла раз.Строго говоря, тогда мы должны добавьте O (1) времени для инициализации индекса цикла и O (1) времени для первого сравнения индекса цикла с пределом, потому что мы тестируем еще раз, чем ходим по кругу.Однако, если невозможно выполнить цикл ноль раз, время для инициализации цикла и тестирования ограничение один раз является членом младшего порядка, который может быть опущен правилом суммирования.

---

Теперь рассмотрим этот пример:

(1) for (j = 0; j < n; j++)
(2)   A[i][j] = 0;

Мы знаем, что строка (1) принимает O(1) время.Очевидно, что мы обходим цикл n раз, как мы можем определить, вычтя нижний предел из верхнего предела, найденного в строке (1), а затем добавив 1.Поскольку тело, строка (2), занимает O (1) времени, мы можем пренебречь временем увеличения j и временем сравнения j с n, оба из которых также равны O (1).Таким образом, время выполнения строк (1) и (2) равно произведение n и O(1), который является O(n).

Аналогично, мы можем ограничить время выполнения внешнего цикла, состоящего из строк (2) - (4), что равно

(2) for (i = 0; i < n; i++)
(3)     for (j = 0; j < n; j++)
(4)         A[i][j] = 0;

Мы уже установили, что цикл из строк (3) и (4) занимает O (n) времени.Таким образом, мы можем пренебречь временем O (1) для увеличения i и проверить, является ли i < n в каждой итерации, заключая, что каждая итерация внешнего цикла занимает O (n) времени.

Инициализация i = 0 внешнего цикла и (n + 1)-я проверка условия i < n аналогично занимает O (1) времени, и им можно пренебречь.Наконец, мы видим, что мы проходим по внешнему циклу n раз, затрачивая O (n) времени на каждую итерацию, что дает общее O(n^2) время работы.

---

Более практичный пример.

Answer 9

Если вы хотите оценить порядок вашего кода эмпирически, а не путем анализа кода, вы могли бы использовать серию возрастающих значений n и время выполнения вашего кода.Рассчитайте свои тайминги в логарифмическом масштабе.Если код равен O(x^ n), значения должны приходиться на линию с наклоном n.

Это имеет ряд преимуществ по сравнению с простым изучением кода.Во-первых, вы можете видеть, находитесь ли вы в диапазоне, где время выполнения приближается к своему асимптотическому порядку.Кроме того, вы можете обнаружить, что некоторый код, который вы считали порядком O (x), на самом деле является порядком O (x ^ 2), например, из-за времени, затраченного на вызовы библиотеки.

Answer 10

По сути, то, что всплывает в 90% случаев, - это просто анализ циклов.Есть ли у вас одинарные, двойные, тройные вложенные циклы?У вас есть O (n), O (n ^ 2), O (n ^ 3) времени выполнения.

Очень редко (если только вы не пишете платформу с обширной базовой библиотекой (как, например, the .NET BCL или STL C ++) вы столкнетесь с чем-то более сложным, чем просто просмотр ваших циклов (для операторов, while, goto и т.д.)

Answer 11

Разбейте алгоритм на части, для которых вам известна нотация big O, и объедините с помощью операторов big O.Это единственный известный мне способ.

Для получения дополнительной информации ознакомьтесь с Страница в Википедии по этому вопросу.

Answer 12

Обозначение Big O полезно, потому что с ним легко работать и оно скрывает ненужные сложности и детали (для некоторого определения ненужного).Одним из хороших способов определения сложности алгоритмов "разделяй и властвуй" является метод дерева.Допустим, у вас есть версия quicksort с процедурой медианы, поэтому вы каждый раз разбиваете массив на идеально сбалансированные подмассивы.

Теперь постройте дерево, соответствующее всем массивам, с которыми вы работаете.В корне у вас есть исходный массив, у корня есть два дочерних элемента, которые являются подмассивами.Повторяйте это до тех пор, пока внизу не появятся одноэлементные массивы.

Поскольку мы можем найти медиану за O (n) раз и разделить массив на две части за O (n) раз, работа, выполняемая на каждом узле, равна O (k), где k - размер массива.Каждый уровень дерева содержит (максимум) весь массив, поэтому работа на уровень равна O (n) (размеры подмассивов в сумме равны n, и поскольку у нас есть O (k) на уровень, мы можем суммировать это).В дереве есть только логарифмические уровни (n), поскольку каждый раз мы уменьшаем входные данные вдвое.

Поэтому мы можем ограничить объем работы сверху с помощью O(n* log (n)).

Однако Big O скрывает некоторые детали, которые мы иногда не можем игнорировать.Рассмотрим вычисление последовательности Фибоначчи с помощью

a=0;
b=1;
for (i = 0; i <n; i++) {
    tmp = b;
    b = a + b;
    a = tmp;
}

и давайте просто предположим, что a и b являются BigIntegers в Java или чем-то таким, что может обрабатывать сколь угодно большие числа.Большинство людей сказали бы, что это алгоритм O (n), не дрогнув.Причина в том, что у вас есть n итераций в цикле for и O (1) работают в стороне от цикла.

Но числа Фибоначчи большие, n-е число Фибоначчи экспоненциально в n, поэтому простое его сохранение займет порядка n байт.Выполнение сложения с большими целыми числами потребует O (n) объема работы.Таким образом, общий объем работы, выполняемой в рамках этой процедуры, составляет

1 + 2 + 3 + ...+ n = n(n-1)/2 = O(n^2)

Таким образом, этот алгоритм выполняется за квадратичное время!

Answer 13

Знакомство с алгоритмами / структурами данных, которые я использую, и / или беглый анализ вложенности итераций.Трудность заключается в том, что когда вы вызываете библиотечную функцию, возможно, несколько раз, вы часто не можете быть уверены в том, вызываете ли вы функцию без необходимости время от времени или какую реализацию они используют.Возможно, библиотечные функции должны иметь показатель сложности / эффективности, будь то Big O или какой-либо другой показатель, который доступен в документации или даже IntelliSense.

Answer 14

Я думаю, что это менее полезно в целом, но для полноты картины есть также Большая Омега Ω, который определяет нижнюю границу сложности алгоритма, и Большая Тета Θ, который определяет как верхнюю, так и нижнюю границу.

Answer 15

Что касается вопроса "как вы вычисляете" Big O, то это часть Теория вычислительной сложности.Для некоторых (многих) особых случаев вы можете использовать некоторые простые эвристики (например, умножение количества циклов для вложенных циклов), особенно.когда все, что вам нужно, - это любая оценка верхней границы, и вы не возражаете, если она будет слишком пессимистичной - я думаю, именно к этому и относится ваш вопрос.

Если вы действительно хотите ответить на свой вопрос по какому-либо алгоритму, лучшее, что вы можете сделать, это применить теорию.Помимо упрощенного анализа "наихудшего случая", я нашел Амортизированный анализ очень полезно на практике.

Answer 16

В 1-м случае выполняется внутренний цикл n-i раз, таким образом, общее количество выполнений равно сумме для i идя от 0 Для n-1 (потому что ниже, а не ниже или равно) n-i.Ты получаешь, наконец, n*(n + 1) / 2, так что O(n²/2) = O(n²).

Для 2-го цикла, i находится между 0 и n входит в комплект для внешнего контура;затем внутренний цикл выполняется, когда j строго больше , чем n, что в таком случае невозможно.

Answer 17

В дополнение к использованию мастер-метода (или одной из его специализаций), я тестирую свои алгоритмы экспериментально.Это не может доказать что достигается какой-либо конкретный класс сложности, но это может обеспечить уверенность в том, что математический анализ является адекватным.Чтобы помочь с этой уверенностью, я использую инструменты покрытия кода в сочетании с моими экспериментами, чтобы убедиться, что я использую все случаи.

В качестве очень простого примера предположим, что вы хотели выполнить проверку работоспособности скорости сортировки списка .NET framework.Вы могли бы написать что-то вроде следующего, затем проанализировать результаты в Excel, чтобы убедиться, что они не превышают n * log (n) кривой.

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

int nCmp = 0;
System.Random rnd = new System.Random();

// measure the time required to sort a list of n integers
void DoTest(int n)
{
   List<int> lst = new List<int>(n);
   for( int i=0; i<n; i++ )
      lst[i] = rnd.Next(0,1000);

   // as we sort, keep track of the number of comparisons performed!
   nCmp = 0;
   lst.Sort( delegate( int a, int b ) { nCmp++; return (a<b)?-1:((a>b)?1:0)); }

   System.Console.Writeline( "{0},{1}", n, nCmp );
}


// Perform measurement for a variety of sample sizes.
// It would be prudent to check multiple random samples of each size, but this is OK for a quick sanity check
for( int n = 0; n<1000; n++ )
   DoTest(n);

Answer 18

Не забудьте также учесть сложности с пространством, которые также могут быть причиной для беспокойства, если у вас ограниченные ресурсы памяти.Так, например, вы можете услышать, что кому-то нужен алгоритм с постоянным пространством, который по сути является способом сказать, что объем пространства, занимаемого алгоритмом, не зависит от каких-либо факторов внутри кода.

Иногда сложность может заключаться в том, сколько раз что-то вызывается, как часто выполняется цикл, как часто выделяется память и так далее - это еще одна часть ответа на этот вопрос.

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

Answer 19

Что часто упускается из виду, так это ожидаемый поведение ваших алгоритмов. Это не меняет сути вашего алгоритма, но это действительно относится к утверждению "преждевременная оптимизация...."

Ожидаемое поведение вашего алгоритма - очень упрощенное - зависит от того, насколько быстро вы можете ожидать, что ваш алгоритм будет работать с данными, которые вы, скорее всего, увидите.

Например, если вы ищете значение в списке, это O (n), но если вы знаете, что в большинстве списков, которые вы видите, ваше значение указано заранее, типичное поведение вашего алгоритма происходит быстрее.

Чтобы действительно разобраться с этим, вы должны быть в состоянии описать распределение вероятностей вашего "пространства ввода" (если вам нужно отсортировать список, как часто этот список уже будет сортироваться?как часто все полностью меняется на противоположное?как часто это в основном сортируется?) Не всегда возможно, чтобы вы это знали, но иногда вы знаете.

Answer 20

отличный вопрос!

Отказ от ответственности:этот ответ содержит ложные утверждения, смотрите комментарии ниже.

Если вы используете большую букву "О", вы говорите о худшем случае (подробнее о том, что это означает позже).Кроме того, существует заглавная тета для среднего случая и большая омега для наилучшего случая.

Загляните на этот сайт, чтобы найти прекрасное формальное определение Big O: https://xlinux.nist.gov/dads/HTML/bigOnotation.html

f (n) = O(g(n)) означает, что существуют положительные константы c и k, такие, что 0 ≤ f (n) ≤ cg (n) для всех n ≥ k.Значения c и k должны быть фиксированными для функции f и не должны зависеть от n.

---

Хорошо, итак, теперь, что мы подразумеваем под сложностями "наилучшего" и "наихудшего" вариантов?

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

Смысл всего этого прилагательноесложность случая заключается в том, что мы ищем способ отобразить количество времени, затраченного гипотетической программой на завершение, в терминах размера конкретных переменных.Однако для многих алгоритмов вы можете утверждать, что не существует единого времени для определенного размера входных данных.Обратите внимание, что это противоречит фундаментальному требованию функции, согласно которому любой входной сигнал должен иметь не более одного выходного сигнала.Итак, мы приходим к следующему множественный функции для описания сложности алгоритма.Теперь, хотя поиск в массиве размером n может занимать разное количество времени в зависимости от того, что вы ищете в массиве, и в зависимости пропорционально от n, мы можем создать информативное описание алгоритма, используя классы наилучшего, среднего и наихудшего вариантов.

Извините, что это так плохо написано и в нем не хватает большого количества технической информации.Но, надеюсь, это облегчит обдумывание классов временной сложности.Как только вы освоитесь с ними, становится простым вопросом синтаксического анализа вашей программы и поиска таких вещей, как циклы for, которые зависят от размеров массива и рассуждений, основанных на ваших структурах данных, какой ввод приведет к тривиальным случаям, а какой - к наихудшим.

Answer 21

Я не знаю, как программно решить это, но первое, что люди делают, это то, что мы пробуем алгоритм для определенных шаблонов по количеству выполненных операций, скажем, 4n ^ 2 + 2n + 1. у нас есть 2 правила:

1. Если у нас есть сумма терминов, то сохраняется термин с наибольшим темпом роста, а остальные термины опускаются.
   
2. Если у нас есть произведение нескольких факторов, постоянные факторы опускаются.

Если мы упростим f(x), где f (x) - формула для количества выполненных операций (4n ^ 2 + 2n + 1, объясненная выше), мы получим значение big-O [в данном случае O (n ^ 2)].Но это должно было бы учитывать интерполяцию Лагранжа в программе, что может быть трудно реализовать.А что, если бы реальное значение big-O было O (2 ^ n), и у нас могло бы быть что-то вроде O (x ^ n), так что этот алгоритм, вероятно, не был бы программируемым.Но если кто -то докажет, что я неправ, дайте мне код....

Answer 22

Для кода A внешний цикл будет выполняться для n+1 время '1' означает процесс, который проверяет, по-прежнему ли i соответствует требованию.И выполняется внутренний цикл n времена, n-2 времена....Таким образом,0+2+..+(n-2)+n= (0+n)(n+1)/2= O(n²).

Для кода B, хотя внутренний цикл не будет вмешиваться и выполнять foo(), внутренний цикл будет выполняться n раз в зависимости от времени выполнения внешнего цикла, которое равно O (n)

Answer 23

Я хотел бы объяснить Big-O в несколько ином аспекте.

Big-O предназначен просто для сравнения сложности программ, что означает, насколько быстро они растут при увеличении входных данных, а не точное время, затрачиваемое на выполнение действия.

ИМХО, в формулах big-O вам лучше не использовать более сложные уравнения (вы могли бы просто придерживаться тех, что приведены на следующем графике). Однако вы все равно можете использовать другую, более точную формулу (например, 3 ^ n, n ^ 3, ...), но более того, иногда это может ввести в заблуждение!Поэтому лучше сделать это как можно проще.

Я хотел бы еще раз подчеркнуть, что здесь мы не хотим получать точную формулу для нашего алгоритма.Мы только хотим показать, как он растет при увеличении входных данных, и сравнить в этом смысле с другими алгоритмами.В противном случае вам лучше использовать другие методы, такие как бенчмарковая разметка.