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

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

时间复杂度O(n)表示程序运行时间跟n有关,并且是线性关系。
空间复杂度O(1),表示所需空间为常量,并且与n无关。

 

例子:

要在 hash 表中找到一个元素就是 O(1)
要在无序数组中找到一个元素就是 O(n)

访问数组的第 n 个元素是 O(1)
访问链表的第 n 个元素是 O(n)

我给你一个简单的判断方法:
如果实现中没有循环就是 O(1)
如果实现中有一个循环就是 O(n)

 

你设计了一个字符串类:客户有时需要知道字符串的长度,
所以有两种设计GetLength()函数的方法
1。每次客户询问长度,你都用循环检测串长,即
for(i=0;str[i]!=0;++i)
这样效率低 时间复杂度O(n)
2 每次串内容改变时才算长度,算好后存起来,以后
客户需要知道字符串的长度就直接把变量值返回
这样效率高 时间复杂度O(1)

 

O(1)复杂度是与输入数据无关,O(n)是与输入数据成正比。
对于程序A,for(int i=0;i<1000;i++),当输入任意的n时循环次数均为1000,复杂度为O(1);
对于程序B,for(int i=0;i<n;i++),当输入任意的n时循环次数为n,复杂度为O(n)。

发表回复

您的电子邮箱地址不会被公开。