Как найти временную сложность алгоритма

The Question

Как найти временную сложность алгоритма?

What have I done before posting a question on SO ?

Я прошелэтот, этот и много других ссылок

Но не там, где я смог найти четкое и прямое объяснение того, как рассчитать сложность времени.

What do I know ?

Скажем для кода так же просто, как показано ниже:

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; Это будет выполнено толькоonce. The time is actually calculated to i=0 а не декларация.

i < N;  Это будет выполненоN+1 раз

i++ ;   Это будет выполненоN раз

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

{1+(N+1)+N} = 2N+2

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

What I want to know ?

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

O(N), O(n2), O(log n), O(n!).... и многоДругой,

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

 msanford10 июн. 2013 г., 00:12
Бонус для тех, кто заинтересован: The Big O Cheat Sheetbigocheatsheet.com
 Mohamed Ennahdi El Idrissi05 мар. 2015 г., 01:10
Проверьте этот блог:mohalgorithmsorbit.blogspot.com, Он охватывает как рекурсивные, так и (особенно) итерационные алгоритмы.
 Dukeling24 дек. 2017 г., 18:39
@Chetan Если вы имеете в виду, что вы должны рассмотретьConsole.Write при вычислении сложности это верно, но также несколько не имеет значения в этом случае, поскольку это только изменяет постоянный коэффициент, который big-O игнорирует (см. ответы), поэтому конечный результат все еще является сложностью O (N) ,
 Dukeling24 дек. 2017 г., 18:24
Связанные / возможно дубликаты:Big O, how do you calculate/approximate it?
 Chetan10 июл. 2017 г., 13:02
почему Console.Write ("Hello World!"); не машинная инструкция?

Ответы на вопрос(8)

http://www.daniweb.com/software-development/computer-science/threads/13488/time-complexity-of-algorithm

The below answer is copied from above (in case the excellent link goes bust)

Наиболее распространенной метрикой для вычисления сложности времени является нотация 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 описывается как O (), где есть мера. Алгоритм быстрой сортировки будет описан как O (N * log (N)).

Обратите внимание, что ни один из них не принял во внимание лучшие, средние и худшие показатели. У каждого будет своя нотация Big O. Также обратите внимание, что это ОЧЕНЬ упрощенное объяснение. Большой О является наиболее распространенным, но он также более сложный, чем я показал. Есть и другие обозначения, такие как большая омега, маленькая буква o и большая тэта. Вы, вероятно, не столкнетесь с ними вне курса анализа алгоритмов. ;)

 04 мар. 2015 г., 09:23
quicksort Алгоритм в худшем случае имеет время выполнения N ^ 2, хотя такое поведение встречается редко.
 17 дек. 2017 г., 10:34
@hiergiltdiestfu Big-O, Big-Omega и т. д. могут применяться к любому из лучших, средних или наихудших вариантов времени выполнения алгоритма.How do O and Ω relate to worst and best case?
 08 мая 2015 г., 09:43
IIRC, little o и big omega используются для определения сложности в лучшем и среднем случае (при большом O - в худшем случае), а также в показателях наилучшего, среднего и худшего случая. Каждый из них будет иметь свою собственную запись Big O & quot; было бы неправильно. Существует еще больше символов с более конкретными значениями, и CS не всегда использует наиболее подходящий символ. Я пришел, чтобы узнать все это по имениLandau symbols Кстати. +1 в любом случае б / с лучший ответ.

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

Как и большинство вещей в жизни, коктейльная вечеринка может помочь нам понять.

O(N)

Когда вы прибываете на вечеринку, вам нужно пожать руку каждому (выполнить операцию над каждым предметом). По количеству участниковN увеличивается, время / работа, которую вам потребуется, чтобы пожать руку каждому, увеличивается по мере того, какO(N).

Why O(N) and not cN?

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

O(N^2)

Ведущий коктейльной вечеринки хочет, чтобы вы играли в глупую игру, где все встречаются со всеми остальными. Поэтому вы должны встретитьсяN-1 другие люди и, поскольку следующий человек уже встретил вас, они должны встретитьсяN-2 люди и тд. Сумма этой серииx^2/2+x/2, По мере роста числа участниковx^2 срок становится большимfastтак что мы просто отбросим все остальное.

O(N^3)

Вы должны встретиться со всеми остальными, и во время каждой встречи вы должны говорить обо всех остальных в комнате.

O(1)

Хозяин хочет что-то объявить. Они звонят в бокал и говорят громко. Все слышат их. Оказывается, это не имеет значения, сколько посетителей, эта операция всегда занимает одинаковое количество времени.

O(log N)

Хозяин выложил всех за стол в алфавитном порядке. Где Дэн? Вы полагаете, что он должен быть где-то между Адамом и Мэнди (конечно, не между Мэнди и Заком!). Учитывая это, он между Джорджем и Мэнди? Нет. Он должен быть между Адамом и Фредом и между Синди и Фредом. И так далее ... мы можем эффективно определить местонахождение Дэна, посмотрев на половину набора, а затем половину этого набора. В конечном счете, мы смотрим наO(log_2 N) физические лица.

O(N log N)

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

Best/Worst Case

Вы прибываете на вечеринку и должны найти Иниго - сколько времени это займет? Это зависит от того, когда вы приедете. Если все вокруг вас толпятся - вы столкнулись с наихудшим случаем: потребуетсяO(N) время. Однако, если все садятся за стол, это займет толькоO(log N) время. Или, может быть, вы можете использовать силу крика бокала хозяина, и это займет всегоO(1) время.

Предполагая, что хост недоступен, мы можем сказать, что алгоритм поиска Inigo имеет нижнюю границуO(log N) и верхняя границаO(N), в зависимости от состояния партии, когда вы приедете.

Space & Communication

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

Кнут написал хорошую статью о первом под названием& quot; Сложность песен & quot;.

Theorem 2: There exist arbitrarily long songs of complexity O(1).

PROOF: (due to Casey and the Sunshine Band). Consider the songs Sk defined by (15), but with

V_k = 'That's the way,' U 'I like it, ' U
U   = 'uh huh,' 'uh huh'

for all k.

используемое для записи временной сложности алгоритма. Когда вы сложите число выполнений в алгоритме, вы получите выражение с результатом, подобным 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)

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

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

Давайте посмотрим, каковы возможности временной сложности алгоритма, вы можете увидеть порядок роста, который я упоминал выше:

Constant time has an order of growth 1, for example: a = b + c.

Logarithmic time has an order of growth LogN, it usually occurs when you're dividing something in half (binary search, trees, even loops), or multiplying something in same way.

Linear, order of growth is N, for example

int p = 0;
for (int i = 1; i < N; i++)
  p = p + 2;

Linearithmic, order of growth is n*logN, usually occurs in divide and conquer algorithms.

Cubic, order of growth N^3, classic example is a triple loop where you check all triplets:

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

Exponential, order of growth 2^N, usually occurs when you do exhaustive search, for example check subsets of some set.

Решение Вопроса

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

Например, давайте посмотрим, как мы упрощаем2N + 2 инструкция машины описать это как простоO(N).

Why do we remove the two 2s ?

Мы заинтересованы в производительности алгоритма, так как N становится большим.

Рассмотрим два слагаемых 2N и 2.

Каково относительное влияние этих двух терминов, когда N становится большим? Предположим, N - миллион.

Тогда первый член равен 2 миллионам, а второй - только 2.

По этой причине мы отбрасываем все, кроме самых больших терминов для больших N.

Итак, теперь мы ушли от2N + 2 в2N.

Традиционно нас интересует только производительностьup to constant factors.

Это означает, что нам действительно все равно, есть ли постоянная кратность различий в производительности, когда N велико. Единица 2N, во всяком случае, недостаточно четко определена. Таким образом, мы можем умножить или разделить на постоянный коэффициент, чтобы получить простейшее выражение.

Так2N становится простоN.

 02 янв. 2016 г., 05:48
Предоставление примера в ответе очень помогло бы будущим читателям. Простая передача ссылки, на которую я должен зарегистрироваться, на самом деле не помогает мне, когда я просто хочу просмотреть какой-нибудь красиво объясненный текст.
 01 окт. 2016 г., 18:45
Я бы посоветовал посмотреть видео доктора Навина Гарга (IIT Delhi Prof.), если вы хотите получить хорошие знания о DS и сложности времени. Проверьте ссылку.nptel.ac.in/courses/106102064
 14 июн. 2012 г., 13:36
Сложность в скобках заключается в том, сколько времени занимает алгоритм, упрощенный с помощью метода, который я объяснил. Мы рассчитываем, сколько времени займет алгоритм, просто сложив количество машинных инструкций, которые он выполнит. Мы можем упростить это, только взглянув на самые загруженные циклы и разделив их на постоянные факторы, как я объяснил.
 25 февр. 2018 г., 03:59
(продолжение) Эта иерархия будет иметь высоту порядка log N. Что касается O (N!), мои аналогии вряд ли ее урежут, но перестановки имеют такой порядок - он непомерно крутой, больше, чем любой полиномиальный или экспоненциальный. Их ровно 10! секунд за шесть недель, но вселенной меньше 20! секунд.
 Yasser14 июн. 2012 г., 13:33
эй, спасибо, что сообщили мне "почему O (2N + 2) к O (N)" очень хорошо объяснил, но это было только частью более крупного вопроса, я хотел, чтобы кто-то указал на какую-то ссылку на скрытый ресурс, или в целом я хотел бы знать, как вы в конечном итоге сталкиваетесь со сложностями времени, такими как O (N), O (n2), O (log n), O (n!) И т. Д. Я знаю, что могу много просить, но все же могу попробовать: {)

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

е один ответ здесь с несколькими примерамиloop.

O(n): Time Complexity of a loop is considered as O(n) if the loop variables is incremented / decremented by a constant amount. For example following functions have O(n) time complexity.

// 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): Time complexity of nested loops is equal to the number of times the innermost statement is executed. For example the following sample loops have O(n^2) time complexity

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
}

For example Selection sort and Insertion Sort have O(n^2) time complexity.

O(Logn) Time Complexity of a loop is considered as O(Logn) if the loop variables is divided / multiplied by a constant amount.

for (int i = 1; i <=n; i *= c) {
   // some O(1) expressions
}
for (int i = n; i > 0; i /= c) {
   // some O(1) expressions
}

For example Binary Search has O(Logn) time complexity.

O(LogLogn) Time Complexity of a loop is considered as O(LogLogn) if the loop variables is reduced / increased exponentially by a constant amount.

// 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
        }
    }    
}

Analysis:

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).

Ref: 1 2 3

Time complexity with examples

сравнения, доступ к элементам массива, присваивание): время выполнения всегда постоянное 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;
Common Running Time

При анализе алгоритма есть некоторые общие времена выполнения:

O(1) – Constant Time Constant time means the running time is constant, it’s not affected by the input size.

O(n) – Linear Time When an algorithm accepts n input size, it would perform n operations as well.

O(log n) – Logarithmic Time Algorithm that has running time O(log n) is slight faster than O(n). Commonly, algorithm divides the problem into sub problems with the same size. Example: binary search algorithm, binary conversion algorithm.

O(n log n) – Linearithmic Time This running time is often found in "divide & conquer algorithms" which divide the problem into sub problems recursively and then merge them in n time. Example: Merge Sort algorithm.

O(n2) – Quadratic Time Look Bubble Sort algorithm!

O(n3) – Cubic Time It has the same principle with O(n2).

O(2n) – Exponential Time It is very slow as input get larger, if n = 1000.000, T(n) would be 21000.000. Brute Force algorithm has this running time.

O(n!) – Factorial Time THE SLOWEST !!! Example : Travel Salesman Problem (TSP)

Взято изЭта статья, Очень хорошо объяснил, должен дать прочитать.

 31 дек. 2015 г., 10:09
Во втором примере вы написалиvisitors = visitors + 1 является1 + 1 = 2, Не могли бы вы объяснить мне, почему вы это сделали?
 12 янв. 2016 г., 10:46
@ Саджиб Ачарья Смотри справа налево. Первый шаг: рассчитатьvisitors + 1   Второй шаг: присвоить значение от первого шага доvisitors   Итак, вышеприведенное выражение состоит из двух утверждений; первый шаг + второй шаг = & gt; 1 + 1 = 2
 13 мар. 2017 г., 20:33
@nbro Почему это 1 + 1 вage = read(x) // (1+1) = 2
 13 мар. 2017 г., 23:46
@Humty Проверьте начало этого ответа:read(x) // O(1) a = 10; // O(1) Во-первых, это вызов функции = & gt; O (1) ///// Второе - это присвоение, как сказал nbro, но 10 - это константа, поэтому секунда - это = & gt; O (1) ...
 13 мар. 2017 г., 20:34
@BozidarSikanjic Почему это 1 + 1 вage = read(x) // (1+1) = 2

Ваш ответ на вопрос