algorithm - эффективности - сложный алгоритм пример




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

Вопрос

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

Что я сделал до публикации вопроса о 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 ,

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


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

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

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

Почему мы удаляем два двух?

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

Рассмотрим два члена 2N и 2.

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

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

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

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

Традиционно нас интересует только производительность до постоянных факторов .

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

Таким образом, 2N становится просто N


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

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.


Хотя есть несколько хороших ответов на этот вопрос. Я хотел бы дать еще один ответ здесь с несколькими примерами 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


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







complexity-theory