时间复杂度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)。