Просмотр анимации, чтобы легко понять временную сложность (1)

алгоритм

Оригинальная ссылка:Просмотр анимации, чтобы легко понять временную сложность (1)

Алгоритм — это набор методов, используемых для обработки данных и решения программных проблем. Для одной и той же задачи, используя разные алгоритмы, конечный результат может быть одинаковым.Например, сортировка имеет первую десятку классической сортировки и несколько странных сортировок.Хотя результаты одинаковы, ресурсы и время, затрачиваемые в процессе, будут Есть большие различия, такие как быстрая сортировка и сортировка обезьян :).

Так как же нам измерить плюсы и минусы разных алгоритмов?

В основном он рассматривается из двух измерений «времени» и «пространства», занимаемых алгоритмом.

  • Измерение времени: относится ко времени, которое требуется для выполнения текущего алгоритма, которое мы обычно описываем как «временную сложность».

  • Пространственное измерение: это относится к тому, сколько памяти требуется для выполнения текущего алгоритма.Мы обычно описываем его как «пространственная сложность».

В этом разделе будет проанализировано измерение «времени».

Что такое Большой О

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

Возможен ли этот путь? Конечно можно, но и у него много недостатков.

Например, старому компьютеру программиста Сяо Ву требуется несколько секунд для обработки данных 10 Вт с помощью пузырьковой сортировки, но iMac Pro читателя может потребоваться всего 0,1 секунды, поэтому ошибка результата очень велика. Более того, некоторые алгоритмы требуют много времени для запуска, и нет никакого способа запустить их полностью, например, обезьянью сортировку :).

Есть ли способ строго проанализировать временную сложность алгоритма?

немного!

«Древние» программисты предложили общий метод: «обозначение большого О», т. е.T(n) = O(f(n)).

где n — размер данных, а O(f(n)) — количество инструкций, которые необходимо выполнить для запуска алгоритма, пропорциональное f(n).

Обозначение Ландау, используемое в приведенной выше формуле, было впервые введено немецким теоретиком чисел Паулем Бахманом в его книге 1892 года «Аналитическая теория чисел» другим немецким теоретиком чисел Эдмундом Ландау (Edmund Landau). Роль нотации Ландау состоит в том, чтобы описывать поведение сложных функций с помощью простых функций, давая верхнюю или нижнюю (точную) оценку. При вычислении сложности алгоритма обычно используется только большой символ О, а маленький символ О, символ Θ и т. д. в системе символов Ландау обычно не используются. Первоначально O здесь была заглавной греческой буквой, но теперь это заглавная английская буква O; маленький символ o также является строчной английской буквой o, а символ Θ поддерживает заглавную греческую букву Θ.

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

Общие показатели временной сложности

Давайте начнем с понимания большого O из общего уровня меры временной сложности:

  • Постоянный порядок O(1)

  • Линейный порядок O (n)

  • Квадратный порядок O (n²)

  • Логарифмический O (logn)

  • Линейный логарифмический порядок O (nlogn)

O(1)

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

void swapTwoInts(int &a, int &b){
  int temp = a;
  a = b;
  b = temp;
}

O(n)

В следующем коде код в цикле for будет выполняться n раз, поэтому время, которое он потребляет, зависит от изменения n, поэтому его временная сложность может быть выражена как O (n).

int sum ( int n ){
   int ret = 0;
   for ( int i = 0 ; i <= n ; i ++){
      ret += i;
   }
   return ret;
}

В частности, c в c * O(n) может быть меньше 1, как в следующем коде:

void reverse ( string &s ) {
    int n = s.size();
    for (int i = 0 ; i < n/2 ; i++){
      swap ( s[i] , s[n-1-i]);
    }
}

O(n²)

Когда есть двойной цикл, то есть код O(n) снова вложен, и его временная сложность равна O(n²).

void selectionSort(int arr[],int n){
   for(int i = 0; i < n ; i++){
     int minIndex = i;
     for (int j = i + 1; j < n ; j++ )
       if (arr[j] < arr[minIndex])
           minIndex = j;
       
     swap ( arr[i], arr[minIndex]);
   }
}

Вот простой вывод

  • Когда i = 0, второй цикл нужно запустить (n - 1) раз.
  • Когда i = 1, второй цикл нужно запустить (n - 2) раз.
  • . . . . . .

Нетрудно получить формулу:

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

Конечно, не все двойные циклы имеют размер O(n²), например следующий вывод 30n раз.Hello,五分钟学算法：）код.

void printInformation (int n ){
   for (int i = 1 ; i <= n ; i++)
        for (int j = 1 ; j <= 30 ; j ++)
           cout<< "Hello,五分钟学算法：）"<< endl;
}

O(logn)

int binarySearch( int arr[], int n , int target){
  int l = 0, r = n - 1;
  while ( l <= r) {
    int mid = l + (r - l) / 2;
    if (arr[mid] == target) return mid;
    if (arr[mid] > target ) r = mid - 1;
    else l = mid + 1;
  }
  return -1;
}

В коде метода бинарного поиска через цикл while диапазон поиска сокращается кратно 2, то есть требуется log2^n раз, чтобы выйти из цикла.

Точно так же следующие два фрагмента кода также имеют временную сложность уровня O(logn).

  // 整形转成字符串
  string intToString ( int num ){
   string s = "";
   // n 经过几次“除以10”的操作后，等于0
   while (num ){
    s += '0' + num%10;
    num /= 10;
   }
   reverse(s)
   return s;
  }

void hello (int n ) {
   // n 除以几次 2 到 1
   for ( int sz = 1; sz < n ; sz += sz) 
     for (int i = 1; i < n; i++)
        cout<< "Hello,五分钟学算法：）"<< endl;
}

O(nlogn)

Если код с временной сложностью O(logn) повторяется N раз, то его временная сложность равна n * O(logn), что равно O(nlogn).

void hello (){
  for( m = 1 ; m < n ; m++){
    i = 1;
    while( i < n ){
        i = i * 2;
    }
   }
}

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

Статья впервые опубликована в публичном аккаунте: Learning Algorithms in Five Minutes

Категории