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