欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

时间复杂度O(1) O(n) O(logn) O(nlogn)是什么意思?

程序员文章站 2022-07-12 22:48:55
...

在你渐渐迷失在你的人生道路上的时候,千万不要因为走的太久,而忘记了我们为什么出发,做码农,也要清楚自己如何才能用有效的土地种植出 出色的产品,于是细节就需要把握一下。

如果你有兴趣可以关注一下公众号 biglead 我的大前端生涯,获取每日学习资料


在描述算法复杂度时,经常用到O(1), O(n), O(logn), O(nlogn)来表示对应复杂度程度,可以用于表示时间复杂度,也用于表示空间复杂度。

类别 描述
O(1) 耗时与输入数据量大小无关
O(n) 数据量增大几倍,耗时也增大几位
O(n^2) 对 n 个数进行排序,需要扫描 n X n 次
O(logn) 当数据量增大 n 倍时 ,扫描次数增大 logn 次(以2为底数)
O(nlogn)

时间复杂度的推导遵循3个原则:

  • 如果运行时间跟n无关,是常数,则时间复杂度是O(1);
  • 只保留时间函数中的最高阶项;
  • 去掉高阶项前面的系数;

1 O(1)

若运行时间跟n的取值无关,即无论n取什么值,我的运行时间都不会变,则时间复杂度为O(1),只要基本操作执行次数是个常量,时间复杂度都为O(1)。

2 O(n)出现情况

O(n)一般出现在只有一个循环的情况下,执行次数是线性的,如下:

public void test(int number) {
	for(int i = 0 ; i < number ; i++) {
		... 其他代码
	}
}

3 O(n^2)出现情况

O(n^2)一般出现在有嵌套循环的情况下

public void test(int n) {
    int a = 1;
    int b = 1;
	for(int i = 0 ; i < n ; i++) {
		for(int j = 0 ; j < n ; j++) {
			a++;
		}
		b++;
	}
}

上术循环中执行次数是 n x n 次 ,时间复制度为O(n^2)