我对 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 大 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)大O长什么样

Answer 1

如果它是以 2 为底的对数，那么重复将 n 除以一半直到它达到 1 是捕获 log(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(n)) 的每个元素进行二进制搜索 (O(log(n))）。

Merge sort is a typical O(n log(n)) algorithm--log(n) 部分将数组拆分为块，O(n) 部分将块合并回一起。对于每个 O(log(n)) 的拆分操作，都会发生 O(n) 的合并，因此复杂性会像在嵌套循环中一样成倍增加。

Answer 2

'log-n' 因素是在考虑分而治之的情况下添加的。其中一些算法设计得最好并且经常使用。

合并排序
堆排序
快速排序
某些基于优化 O(n^2) 算法的分而治之算法

我对 n*log(N) Big O 的样子很感兴趣

I am interested in what n*log(N) Big O looks like

c

big-o

time-complexity