c - 我对 n*log(N) Big O 的样子很感兴趣
问题描述
我知道简单的线性大 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 的样子。
解决方案
如果它是 log base 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))。
合并排序是一种典型的 O(n log(n)) 算法——log(n) 部分将数组拆分为块,而 O(n) 部分将块合并在一起。对于每个 O(log(n)) 拆分操作,都会发生 O(n) 合并,因此复杂性会像嵌套循环一样相乘。
推荐阅读
- python - 通过泰勒展开估计 pi 的错误
- julia - 在 Julia 中将标记形状提供为 Int
- python - 无法在 Juypter Notebook 中导入 PyOpenCL
- instance - 如何将时间实例添加到本体
- vue.js - vue-cli 的问题:找不到模块'@babel/preset-env/data/built-ins.json'
- python - 递归二分搜索以检索目标的索引
- python - H2O.ai import_file 看起来不像懒惰的评估,它在做什么?
- jenkins - 詹金斯主页上的 ERR_CONNECTION_TIMED_OUT
- python - Python,使用 Popen 提交 qsub 作业
- unity3d - NPC不断走进墙壁 - Unity2D