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




алгоритмов максимума (9)

Вопрос

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

Что я сделал до публикации вопроса о SO?

Я прошел через this , this и многие другие ссылки

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

Что я знаю ?

Скажите, что код такой же простой, как приведенный ниже:

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 а не декларации.

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

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

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

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

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

Что я хочу знать?

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

O (N), O (n2), O (log n), O (n!) .... и многие other ,

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


Answers

Сложность времени с примерами

1 - Основные операции (арифметика, сравнение, доступ к элементам массива, назначение): Время работы всегда постоянное O (1)

Пример :

read(x)                               // O(1)
a = 10;                               // O(1)
a = 1.000.000.000.000.000.000         // O(1)

2 - Если then else statement: Выполняется только максимальное время работы от двух или более возможных операторов.

Пример:

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. Таким образом, его большая oh по-прежнему остается постоянной T (n) = O (1).

3 - Looping (для, while, repeat): Время выполнения для этого оператора - это число циклов, умноженное на количество операций внутри этого цикла.

Пример:

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;

Общее время выполнения

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

  1. O (1) - Постоянное время Постоянное время означает, что время работы постоянное, на него не влияет размер ввода .

  2. O (n) - Линейное время Когда алгоритм принимает n размер ввода, он также выполняет n операций.

  3. O (log n) - Логарифмический алгоритм времени, который имеет время работы O (log n), немного быстрее, чем O (n). Обычно алгоритм делит проблему на подвыборы с одинаковым размером. Пример: алгоритм двоичного поиска, алгоритм двоичного преобразования.

  4. O (n log n) - Линеаритическое время Это время работы часто встречается в «алгоритмах разделения и покорения», которые рекурсивно делят проблему на подвыборы, а затем объединяют их в n раз. Пример: алгоритм слияния сортировки.

  5. O (n 2 ) - алгоритм сортировки по квадратичному времени Look Bubble!

  6. O (n 3 ) - Кубическое время Он имеет тот же принцип с O (n 2 ).

  7. O (2 n ) - Экспоненциальное время Это очень медленно, когда вход становится больше, если n = 1000.000, T (n) будет 21000.000. Алгоритм Brute Force имеет это время работы.

  8. O (n!) - Факториальное время МЕДЛЕННОЕ !!! Пример: проблема с продавцом (TSP)

Взято из этой статьи . Очень хорошо объясняемый должен дать прочитать.


Взято отсюда - Введение во временную сложность алгоритма

1. Введение

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

2. Обозначение Big O

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

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

Несколько примеров:

  • 1 = O (n)
  • n = O (n 2 )
  • log (n) = O (n)
  • 2 n + 1 = O (n)

3. O (1) Постоянное время:

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

Примеры:

  • array: доступ к любому элементу
  • фиксированный размер: push и pop
  • очередь с фиксированным размером: методы очереди и деактивации

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) Логарифмическое время:

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

Пример: двоичный поиск

Вспомните игру «двадцать вопросов» - задача - угадать значение скрытого числа в интервале. Каждый раз, когда вы догадываетесь, вам говорят, слишком ли высока или слишком низкая ваша догадка. Игра «20 вопросов» подразумевает стратегию, которая использует ваше количество предположений, чтобы уменьшить размер интервала в два раза. Это пример общего метода решения проблем, известного как бинарный поиск

6. O (n2) Квадратичное время

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

Примеры:

7. Некоторые полезные ссылки


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

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

НА)

Когда вы приходите на вечеринку, вы должны пожать всем руку (выполнять операцию над каждым предметом). По мере увеличения числа участников 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 (log 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'

для всех k.


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)


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

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

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

  • Постоянное время имеет порядок роста 1 , например: a = b + c .

  • Логарифмическое время имеет порядок роста LogN , обычно это происходит, когда вы 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 , обычно возникает, когда вы выполняете исчерпывающий поиск, например, проверяете подмножества некоторого набора.


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


Это отличная статья: 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 является наиболее распространенным, но он также более сложный, чем я показал. Существуют и другие обозначения, такие как большая омега, маленькая о и большая тета. Вероятно, вы не столкнетесь с ними вне курса анализа алгоритмов. ;)


Хотя есть несколько хороших ответов на этот вопрос. Я хотел бы дать еще один ответ здесь с несколькими примерами loop .

  • O (n) : Time Сложность цикла рассматривается как 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) Time Сложность цикла рассматривается как 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
    }
    

    Например, Binary Search имеет сложность времени O (Logn) .

  • O (LogLogn) Time Сложность цикла рассматривается как 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 2 3


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

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

В статье « Инженерные алгоритмы планирования быстрого маршрута» дается обзор хода исследований в этой области. Дополнительную информацию см. В ссылках на этот документ.

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

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

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







algorithm time-complexity complexity-theory