Меня интересует, как выглядит n * log (N) Big O

Question

Я знаю, что простой линейный Big O выглядит так (все это в C):

#include <stdio.h>    
int main()
{
    int array[10]={1,2,3,4,5,6,7,8,9,10}; //elements of the array
    int a; //creating the new variables
    for (a=0;a<10;a++){
            printf("%d\n", array[a]); //print elements of the array

    }
}

И я знаю, что N ^ 2 Big O выглядит так:

#include <stdio.h>   
int main()
{
    int array[10]={1,2,3,4,5,6,7,8,9,10}; //elements of the array
    int a,b; //creating the two variables
    for (a=0;a<10;a++){ //do stuff
        for (b=0;b<10;b++){ //do stuff
            printf("%d = %d\n", array[a],array[b]); //print elements of the array
        }
    }
}

Меня интересует, как выглядит n * log (n) Big O.

Answer 1

Если это лог-база 2, то деление n наполовину несколько раз, пока оно не достигнет 1, является наиболее типичным способом записи сложности журнала (n):

for (int i = n; i > 0; i /= 2);

Итак O (n log ( n)) будет выглядеть следующим образом:

for (int i = 0; i < n; i++) {
  for (int j = n; j > 0; j /= 2) {
    // O(1) work
  }
}

Концептуально это похоже на выполнение двоичного поиска (O (log (n)) для каждого элемента массива (O (n)).

Сортировка слиянием - это типичный алгоритм O (n log (n)) - часть log (n) разделяет массив на части и часть O (n) объединяет фрагменты вместе. Для каждой операции разделения O (log (n)) происходит объединение O (n), поэтому сложности умножаются вместе, как во вложенном l oop.

Answer 2

Коэффициент 'log-n' добавляется с учетом разделения и завоевания. Некоторые из этих алгоритмов лучше всего разработаны и часто используются.

1. Сортировка слиянием
2. Сортировка кучи
3. Быстрая сортировка
4. Определенные алгоритмы разделения и завоевания на основе алгоритмов оптимизации O (n ^ 2)