Как найти временную сложность алгоритма
Вопрос
Как найти временную сложность алгоритма?
Что я сделал, прежде чем опубликовать вопрос о SO?
Я прошел через это, это и многие другие ссылки
Но не там, где я смог найти четкое и прямое объяснение того, как рассчитать сложность времени.
Что я знаю?
Скажем для кода так же просто, как показано ниже:
char h = 'y'; // This will be executed 1 time
int abc = 0; // This will be executed 1 time
Скажите для цикла, как показано ниже:
for (int i = 0; i < N; i++) {
Console.Write('Hello World !');
}
int i = 0; Это будет выполнено только один раз. Время фактически рассчитывается до i=0 а не декларация.
я
я ++; Это будет выполнено N раз
Таким образом, количество операций, необходимых для этого цикла
{1+(N+1)+N} = 2N+2
Примечание: это все еще может быть неправильно, так как я не уверен в своем понимании расчета сложности времени
Что я хочу знать?
Итак, эти небольшие базовые вычисления, я думаю, я знаю, но в большинстве случаев я видел сложность времени как
O (N), O (n2), O (log n), O (n!).... и многие другие,
Может кто-нибудь помочь мне понять, как можно рассчитать временную сложность алгоритма? Я уверен, что есть много новичков, таких как я, которые хотят это знать.
11 ответов
Как найти временную сложность алгоритма
Вы складываете, сколько машинных инструкций он будет выполнять, в зависимости от размера его ввода, а затем упрощаете выражение до наибольшего (когда N очень большое) члена и может включать любой упрощающий постоянный коэффициент.
Например, давайте посмотрим, как мы упрощаем 2N + 2 инструкция машины, чтобы описать это как просто O(N),
Почему мы удаляем два 2 с?
Мы заинтересованы в производительности алгоритма, так как N становится большим.
Рассмотрим два слагаемых 2N и 2.
Каково относительное влияние этих двух терминов, когда N становится большим? Предположим, N - миллион.
Тогда первый член равен 2 миллионам, а второй - только 2.
По этой причине мы отбрасываем все, кроме самых больших терминов для больших N.
Итак, теперь мы ушли от 2N + 2 в 2N,
Традиционно мы заинтересованы только в производительности до постоянных факторов.
Это означает, что нам не важно, есть ли постоянная кратность различий в производительности, когда N велико. Единица 2N, во всяком случае, не очень четко определена. Таким образом, мы можем умножить или разделить на постоянный коэффициент, чтобы получить простейшее выражение.
Так 2N становится просто N,
Это отличная статья: http://www.daniweb.com/software-development/computer-science/threads/13488/time-complexity-of-algorithm
Приведенный ниже ответ скопирован сверху (в случае, если отличная ссылка обанкротится)
Наиболее распространенной метрикой для вычисления сложности времени является нотация Big O. Это устраняет все постоянные факторы, так что время работы можно оценить по отношению к N, когда N приближается к бесконечности. В общем, вы можете думать об этом так:
statement;
Постоянно. Время выполнения оператора не изменится по отношению к N.
for ( i = 0; i < N; i++ )
statement;
Является линейным. Время работы цикла прямо пропорционально N. Когда N удваивается, то же самое происходит и время работы.
for ( i = 0; i < N; i++ ) {
for ( j = 0; j < N; j++ )
statement;
}
Является квадратичным Время работы двух петель пропорционально квадрату N. Когда N удваивается, время работы увеличивается на N * N.
while ( low <= high ) {
mid = ( low + high ) / 2;
if ( target < list[mid] )
high = mid - 1;
else if ( target > list[mid] )
low = mid + 1;
else break;
}
Логарифмический Время выполнения алгоритма пропорционально числу делений N на 2. Это происходит потому, что алгоритм делит рабочую область пополам с каждой итерацией.
void quicksort ( int list[], int left, int right )
{
int pivot = partition ( list, left, right );
quicksort ( list, left, pivot - 1 );
quicksort ( list, pivot + 1, right );
}
Есть N * log ( N). Время выполнения состоит из N циклов (итеративных или рекурсивных), которые являются логарифмическими, поэтому алгоритм представляет собой комбинацию линейных и логарифмических.
В общем, выполнение чего-либо с каждым элементом в одном измерении является линейным, выполнение чего-либо с каждым элементом в двух измерениях является квадратичным, а деление рабочей области пополам - логарифмическим. Существуют и другие меры Big O, такие как кубическая, экспоненциальная и квадратный корень, но они не так часто встречаются. Обозначение Big O описывается как O (), где есть мера. Алгоритм быстрой сортировки будет описан как O ( N * log ( N)).
Обратите внимание, что ни один из них не принял во внимание лучшие, средние и худшие показатели. У каждого будет своя нотация Big O. Также обратите внимание, что это ОЧЕНЬ упрощенное объяснение. Big O является наиболее распространенным, но он также более сложный, что я показал. Есть и другие обозначения, такие как большая омега, маленькая буква o и большая тэта. Вы, вероятно, не встретите их вне курса анализа алгоритма.;)
Взято отсюда - Введение во временную сложность алгоритма
1. Введение
В информатике временная сложность алгоритма количественно определяет количество времени, затрачиваемое алгоритмом на выполнение, как функцию длины строки, представляющей входные данные.
2. Большая О запись
Временная сложность алгоритма обычно выражается с использованием больших обозначений O, что исключает коэффициенты и члены более низкого порядка. Когда выражено таким образом, говорят, что временная сложность описывается асимптотически, т. Е. Размер входного сигнала стремится к бесконечности.
Например, если время, требуемое алгоритмом на всех входах размера n, составляет не более 5n3 + 3n, асимптотическая сложность времени составляет O (n3). Подробнее об этом позже.
Еще несколько примеров:
- 1 = O (n)
- n = O (n2)
- log (n) = O (n)
- 2 n + 1 = O (n)
3. O (1) постоянное время:
Говорят, что алгоритм работает в постоянном времени, если ему требуется одинаковое количество времени независимо от размера ввода.
Примеры:
- массив: доступ к любому элементу
- стек фиксированного размера: методы push и pop
- очередь фиксированного размера: методы enqueue и dequeue
4. O(n) линейное время
Говорят, что алгоритм работает за линейное время, если его время выполнения прямо пропорционально размеру входа, то есть время растет линейно с увеличением размера входа.
Рассмотрим следующие примеры: ниже я линейно ищу элемент, который имеет временную сложность O(n).
int find = 66;
var numbers = new int[] { 33, 435, 36, 37, 43, 45, 66, 656, 2232 };
for (int i = 0; i < numbers.Length - 1; i++)
{
if(find == numbers[i])
{
return;
}
}
Больше примеров:
- Массив: линейный поиск, обход, поиск минимума и т. Д.
- ArrayList: содержит метод
- Очередь: содержит метод
5. O(log n) Логарифмическое время:
Говорят, что алгоритм работает в логарифмическом времени, если его время выполнения пропорционально логарифму входного размера.
Пример: бинарный поиск
Вспомните игру "двадцать вопросов" - задача состоит в том, чтобы угадать значение скрытого числа в интервале. Каждый раз, когда вы делаете предположение, вам говорят, является ли ваше предположение слишком высоким или слишком низким. Игра "Двадцать вопросов" подразумевает стратегию, которая использует ваше число догадок, чтобы уменьшить размер интервала вдвое. Это пример общего метода решения проблем, известного как бинарный поиск
6. O(n2) квадратичное время
Говорят, что алгоритм выполняется за квадратичное время, если его время выполнения пропорционально квадрату входного размера.
Примеры:
7. Некоторые полезные ссылки
Хотя есть несколько хороших ответов на этот вопрос. Я хотел бы дать еще один ответ здесь с несколькими примерами loop,
O (n): временная сложность цикла рассматривается как O (n), если переменные цикла увеличиваются / уменьшаются на постоянную величину. Например, следующие функции имеют O (n) временную сложность.
// Here c is a positive integer constant for (int i = 1; i <= n; i += c) { // some O(1) expressions } for (int i = n; i > 0; i -= c) { // some O(1) expressions }O (n ^ c): временная сложность вложенных циклов равна числу выполнений самого внутреннего оператора. Например, следующие примеры циклов имеют O(n^2) временную сложность
for (int i = 1; i <=n; i += c) { for (int j = 1; j <=n; j += c) { // some O(1) expressions } } for (int i = n; i > 0; i += c) { for (int j = i+1; j <=n; j += c) { // some O(1) expressions }Например, сортировка по выбору и сортировка по вставке имеют временную сложность O(n^2).
ВремяO(Logn) Сложность цикла рассматривается как O(Logn), если переменные цикла делятся / умножаются на постоянную величину.
for (int i = 1; i <=n; i *= c) { // some O(1) expressions } for (int i = n; i > 0; i /= c) { // some O(1) expressions }Например, бинарный поиск имеет сложность времени O(Logn).
O (LogLogn) Время Сложность цикла рассматривается как O (LogLogn), если переменные цикла уменьшаются / увеличиваются экспоненциально на постоянную величину.
// Here c is a constant greater than 1 for (int i = 2; i <=n; i = pow(i, c)) { // some O(1) expressions } //Here fun is sqrt or cuberoot or any other constant root for (int i = n; i > 0; i = fun(i)) { // some O(1) expressions }
Один пример анализа сложности времени
int fun(int n)
{
for (int i = 1; i <= n; i++)
{
for (int j = 1; j < n; j += i)
{
// Some O(1) task
}
}
}
Анализ:
For i = 1, the inner loop is executed n times.
For i = 2, the inner loop is executed approximately n/2 times.
For i = 3, the inner loop is executed approximately n/3 times.
For i = 4, the inner loop is executed approximately n/4 times.
…………………………………………………….
For i = n, the inner loop is executed approximately n/n times.
Таким образом, общая временная сложность вышеуказанного алгоритма (n + n/2 + n/3 + … + n/n), Который становится n * (1/1 + 1/2 + 1/3 + … + 1/n)
Важная вещь о сериале (1/1 + 1/2 + 1/3 + … + 1/n) равно O(Logn). Таким образом, временная сложность приведенного выше кода составляет O (nLogn).
Сложность времени с примерами
1 - Основные операции (арифметика, сравнения, доступ к элементам массива, присваивание): время выполнения всегда постоянное O(1)
Пример:
read(x) // O(1)
a = 10; // O(1)
a = 1.000.000.000.000.000.000 // O(1)
2 - оператор If then else: берется только максимальное время выполнения из двух или более возможных операторов.
Пример:
age = read(x) // (1+1) = 2
if age < 17 then begin // 1
status = "Not allowed!"; // 1
end else begin
status = "Welcome! Please come in"; // 1
visitors = visitors + 1; // 1+1 = 2
end;
Таким образом, сложность вышеприведенного псевдокода T(n) = 2 + 1 + max(1, 1+2) = 6. Таким образом, его большое число o остается постоянным T (n) = O(1).
3 - Цикл (для, пока, повтор): время выполнения для этого оператора - это количество циклов, умноженное на количество операций внутри этого цикла.
Пример:
total = 0; // 1
for i = 1 to n do begin // (1+1)*n = 2n
total = total + i; // (1+1)*n = 2n
end;
writeln(total); // 1
Таким образом, его сложность T(n) = 1+4n+1 = 4n + 2. Таким образом, T (n) = O (n).
4 - Вложенный цикл (цикл внутри цикла): поскольку внутри основного цикла есть хотя бы один цикл, время выполнения этого оператора использовалось O(n^2) или O(n^3).
Пример:
for i = 1 to n do begin // (1+1)*n = 2n
for j = 1 to n do begin // (1+1)n*n = 2n^2
x = x + 1; // (1+1)n*n = 2n^2
print(x); // (n*n) = n^2
end;
end;
Общее время выполнения
При анализе алгоритма есть некоторые общие времена выполнения:
O(1) - Постоянное время Постоянное время означает, что время работы постоянно, оно не зависит от размера входа.
O (n) - Линейное время Когда алгоритм принимает n входного размера, он также будет выполнять n операций.
O (log n) - Алгоритм логарифмического времени, время работы которого O (log n), немного быстрее, чем O (n). Обычно алгоритм делит задачу на подзадачи с одинаковым размером. Пример: алгоритм двоичного поиска, алгоритм двоичного преобразования.
O (n log n) - линейное время. Это время выполнения часто встречается в "алгоритмах" разделяй и властвуй ", которые рекурсивно делят задачу на подзадачи, а затем объединяют их за n времени. Пример: алгоритм сортировки слиянием.
O (n2) - Алгоритм пузырьковой сортировки с квадратичным временем!
O (n3) - кубическое время. Он имеет тот же принцип, что и O (n2).
O (2n) - экспоненциальное время. Это очень медленно, так как ввод увеличивается, если n = 1000.000, T(n) будет 21000.000. Алгоритм грубой силы имеет это время выполнения.
O (n!) - Факториальное время САМЫЙ МЕДЛЕННЫЙ!!! Пример: задача коммивояжера (TSP)
Взято из этой статьи. Очень хорошо объяснил, должен дать прочитать.
Когда вы анализируете код, вы должны анализировать его построчно, подсчитывая каждую операцию / распознавая сложность времени, в конце вы должны суммировать его, чтобы получить полную картину.
Например, у вас может быть один простой цикл с линейной сложностью, но позже в той же программе вы можете иметь тройной цикл с кубической сложностью, поэтому ваша программа будет иметь кубическую сложность. Функция порядка роста вступает в игру прямо здесь.
Давайте посмотрим, каковы возможности временной сложности алгоритма, вы можете увидеть порядок роста, который я упомянул выше:
Постоянное время имеет порядок роста
1, например:a = b + c,Логарифмическое время имеет порядок роста
LogNобычно это происходит, когда вы делите что-то пополам (двоичный поиск, деревья, даже циклы) или умножаете что-то таким же образом.Линейный, порядок роста
N, напримерint p = 0; for (int i = 1; i < N; i++) p = p + 2;Линейный, порядок роста
n*logN, обычно происходит в алгоритмах разделяй и властвуй.Куб, порядок роста
N^3Классическим примером является тройной цикл, где вы проверяете все триплеты:int x = 0; for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) for (int k = 0; k < N; k++) x = x + 2Экспоненциальный, порядок роста
2^Nобычно происходит, когда вы выполняете исчерпывающий поиск, например, проверяете подмножества некоторого набора.
Грубо говоря, временная сложность - это способ суммировать, как количество операций или время выполнения алгоритма увеличивается с увеличением размера входных данных.
Как и большинство вещей в жизни, коктейльная вечеринка может помочь нам понять.
НА)
Когда вы прибываете на вечеринку, вы должны пожать руку каждому (выполнить операцию на каждом предмете). По количеству участников N увеличивается, время / работа, которую вам потребуется, чтобы пожать руку каждому, увеличивается по мере O(N),
Зачем O(N) и не cN ?
Существует разное количество времени, которое требуется, чтобы пожать руку людям. Вы могли бы усреднить это и зафиксировать это в постоянной c, Но основная операция здесь - рукопожатие со всеми - всегда будет пропорциональна O(N), не важно что c было. При обсуждении вопроса о том, стоит ли нам идти на коктейльную вечеринку, мы часто больше заинтересованы в том, чтобы нам приходилось встречаться со всеми, чем в мельчайших подробностях того, как эти встречи выглядят.
O (N ^ 2)
Ведущий коктейльной вечеринки хочет, чтобы вы играли в глупую игру, где все встречаются со всеми остальными. Поэтому вы должны встретиться N-1 другие люди и, поскольку следующий человек уже встретил вас, они должны встретиться N-2 люди и тд. Сумма этой серии x^2/2+x/2, По мере роста количества участников x^2 срок быстро растет, поэтому мы просто отбрасываем все остальное.
O (N ^ 3)
Вы должны встретиться со всеми остальными, и во время каждой встречи вы должны говорить обо всех остальных в комнате.
O (1)
Хозяин хочет что-то объявить. Они звонят в бокал и громко разговаривают. Все слышат их. Оказывается, неважно, сколько посетителей, эта операция всегда занимает одинаковое количество времени.
O (журнал N)
Хозяин выложил всех за стол в алфавитном порядке. Где Дэн? Вы полагаете, что он должен быть где-то между Адамом и Мэнди (конечно, не между Мэнди и Заком!). Учитывая это, он между Джорджем и Мэнди? Он должен быть между Адамом и Фредом и между Синди и Фредом. И так далее... мы можем эффективно найти Дэна, посмотрев на половину набора, а затем половину этого набора. В конечном счете, мы смотрим на O(log_2 N) лиц.
O(N log N)
Вы можете найти, где сесть за стол, используя алгоритм выше. Если большое количество людей пришло к столу, по одному, и все сделали это, это заняло бы O(N log N) времени. Оказывается, это время, необходимое для сортировки любой коллекции элементов, когда они должны сравниваться.
Лучший / худший случай
Вы прибываете на вечеринку и должны найти Иниго - сколько времени это займет? Это зависит от того, когда вы приедете. Если все вокруг толпятся, вы столкнулись с наихудшим случаем: O(N) время. Однако, если все садятся за стол, это займет только O(log N) время. Или, может быть, вы можете использовать силу крика бокала хозяина, и это займет всего O(1) время.
Предполагая, что хост недоступен, мы можем сказать, что алгоритм поиска Inigo имеет нижнюю границу O(log N) и верхняя граница O(N), в зависимости от состояния партии, когда вы приедете.
Космос и связь
Те же идеи могут быть применены к пониманию того, как алгоритмы используют пространство или связь.
Кнут написал хорошую статью о первом под названием "Сложность песен".
Теорема 2: Существуют произвольно длинные песни сложности O(1).
ДОКАЗАТЕЛЬСТВО: (из-за Кейси и Саншайн Бэнд). Рассмотрим песни Sk, определенные в (15), но с
V_k = 'That's the way,' U 'I like it, ' U
U = 'uh huh,' 'uh huh'
для всех к.
Я знаю, что этот вопрос уходит в прошлое, и здесь есть несколько отличных ответов, тем не менее, я хотел бы поделиться еще одним моментом для математически мыслящих людей, которые будут натыкаться на этот пост. Основная теорема - еще одна полезная вещь, которую нужно знать при изучении сложности. Я не видел, чтобы это упоминалось в других ответах.
O(n) - это большое обозначение O, используемое для записи временной сложности алгоритма. Когда вы сложите количество выполнений в алгоритме, вы получите выражение с результатом, например 2N + 2, в этом выражении N является доминирующим термином (термин, оказывающий наибольшее влияние на выражение, если его значение увеличивается или уменьшается). Теперь O (N) - временная сложность, а N - доминирующий член. пример
For i= 1 to n;
j= 0;
while(j<=n);
j=j+1;
здесь общее количество выполнений для внутреннего цикла равно n + 1, а общее количество выполнений для внешнего цикла равно n (n + 1) / 2, поэтому общее количество выполнений для всего алгоритма равно n+1+n(n+1/2).) = (n^2 + 3n) / 2. здесь n^2 является доминирующим слагаемым, поэтому временная сложность для этого алгоритма составляет O (n^2)
Другие ответы сосредоточены на большой O-нотации и практических примерах. Я хочу ответить на вопрос, подчеркнув теоретическую точку зрения. В приведенном ниже объяснении обязательно отсутствуют детали; отличным источником для изучения теории сложности вычислений является «Введение в теорию вычислений» Майкла Сипсера.
Машины Тьюринга
Наиболее распространенной моделью для исследования любого вопроса о вычислениях является машина Тьюринга. Машина Тьюринга имеет одномерную ленту, состоящую из символов, которая используется как запоминающее устройство. Он имеет ленточную головку, которая используется для записи и чтения с ленты. У него есть таблица переходов, определяющая поведение машины, которая представляет собой фиксированный аппаратный компонент, определяемый при создании машины. Машина Тьюринга работает с дискретными временными шагами, делая следующее:
Он читает символ под головкой ленты. В зависимости от символа и его внутреннего состояния, которое может принимать только конечное число значений, он считывает три значения s, σ и X из своей таблицы переходов, где s — внутреннее состояние, σ — символ, а X — либо Right, либо Левый.
Он меняет свое внутреннее состояние на s.
Он меняет прочитанный символ на σ.
Он перемещает головку ленты на один шаг в соответствии с направлением по оси X.
Машины Тьюринга — мощные модели вычислений. Они могут делать все то же, что и ваш цифровой компьютер. Они были введены до появления современных цифровых компьютеров отцом теоретической информатики и математиком Аланом Тьюрингом.
Сложность времени
Трудно определить временную сложность одной задачи типа «Есть ли у белых выигрышная стратегия в шахматах?» потому что есть машина, которая работает на один шаг и дает правильный ответ: либо машина, которая прямо говорит «нет», либо прямо «да». Чтобы заставить его работать, мы вместо этого определяем временную сложность семейства задач L , каждая из которых имеет размер, обычно длину описания проблемы. Затем возьмем машину Тьюринга M , которая правильно решает все задачи в этом семействе. Когда M дается задача этого семейства размера n , он решает ее за конечное число шагов. Назовем f(n) максимально возможным временем, которое требуется M для решения задач размера n .. Тогда мы говорим, что временная сложность L равна O(f(n)) , а это означает, что существует машина Тьюринга, которая будет решать ее экземпляр размера n не более чем за время Cf(n) , где C — независимая константа. из н .
Разве это не зависит от машин? Могут ли цифровые компьютеры сделать это быстрее?
Да! Некоторые проблемы могут быть решены быстрее с помощью других моделей вычислений, например, две ленточные машины Тьюринга решают некоторые задачи быстрее, чем машины с одной лентой. Вот почему теоретики предпочитают использовать надежные классы сложности, такие как NL, P, NP, PSPACE, EXPTIME и т. д. Например, P — это класс задач принятия решений, временная сложность которых равна O(p(n)), где p — многочлен . Класс P не изменится, даже если вы добавите в машину Тьюринга десять тысяч лент или используете другие типы теоретических моделей, например машины с произвольным доступом.
Разница в теории и практике
Обычно предполагается, что временная сложность сложения целых чисел составляет O(1). Это предположение имеет смысл на практике, потому что компьютеры используют фиксированное количество битов для хранения чисел для многих приложений. Нет причин предполагать такое в теории, поэтому временная сложность сложения равна O(k), где k — количество битов, необходимых для выражения целого числа.
Нахождение временной сложности класса задач
Самый простой способ показать временную сложность задачи — O(f(n)) — построить машину Тьюринга, которая решает ее за время O(f(n)) . Создание машин Тьюринга для решения сложных задач — нетривиальная задача; нужно некоторое знакомство с ними. Таблица переходов для машины Тьюринга редко приводится и описывается на высоком уровне. Становится легче увидеть, сколько времени потребуется машине, чтобы остановиться, когда вы ознакомитесь с ними.
Показать, что проблема не является O(f(n)) временной сложностью, — это совсем другая история... Несмотря на то, что есть некоторые результаты, такие как теорема об иерархии времени , здесь есть много открытых проблем. Например, вопрос о том, относятся ли задачи из NP к P, т.е. решаемы ли они за полиномиальное время, является одной из семи проблем математики, получивших премию тысячелетия, за решение которой будет присужден 1 миллион долларов.
Чтобы получить представление об алгоритме, я часто делаю это экспериментально. Просто измените вход N и посмотрите, сколько времени займет вычисление. Это требует некоторого размышления, поскольку big-O описывает временную сложность алгоритма для наихудшего случая, и найти наихудший случай может быть сложно.
Делая это теоретически, ваш подход кажется мне правильным: пройтись по программе (всегда выбирая наиболее сложный по времени путь), добавить индивидуальные времена и избавиться от всех констант / факторов. Вложенные циклы, прыжки и т. Д. Могут сделать это довольно сложным, но я не могу придумать серебряную пулю, чтобы решить это иначе.
Вас также могут заинтересовать http://en.wikipedia.org/wiki/Big_O_notation, хотя это довольно математично.
Я также только что нашел http://en.wikipedia.org/wiki/Analysis_of_algorithms