可能是重复的问题:
Big O的简单解释
当我们谈论算法的时间复杂度时,有时也会考虑到内存。我想知道big-O(1)、big-O(n)、big-O(n*n)内存的含义是什么?
以及它们与时间复杂度的关系如何?
可能是重复的问题:
Big O的简单解释
当我们谈论算法的时间复杂度时,有时也会考虑到内存。我想知道big-O(1)、big-O(n)、big-O(n*n)内存的含义是什么?
以及它们与时间复杂度的关系如何?
正如xmoex所说:
o(1)表示常数级别的内存使用,因此输入量大小并不重要。
o(n)表示线性内存使用,因此输入量增加会导致内存线性增加。
o(n*n)表示二次内存使用,因此输入量增加会导致内存呈平方级别增加(平均为x^2)。
大多数情况下,这种内存复杂度与时间复杂度是完全独立的。对于计算机算法来说,了解算法如何管理这两个复杂度是很重要的,以决定算法的质量。但是,这两个复杂度必须分别计算。根据问题的使用情况和环境,其中一个可能比另一个更重要。
o(1)表示平均内存使用是固定的,不管您的输入大小如何
o(n)表示如果您正在处理n个元素,则您的平均内存需求会线性增长
o(n*n)表示如果您正在处理n个元素,则您的平均内存需求将呈二次增长
有一篇维基百科文章介绍了所谓的大O符号(也涵盖了小o…)
在记忆方面,复杂性意味着当要处理的项目数量增加时,所需内存大小的增长速度。一个很好的例子是排序算法。
O(1)
和O(log n)
表示,在对N个项目进行排序时,算法需要的内存少于为N个项目分配的总内存。(即原地排序)O(n)
-内存消耗是线性的,因此随着项目计数的增长而增长内存消耗O(n*n)
表示算法需要更多的额外内存。这里有人解释了大O符号的含义。因此,我不会再重复解释。但是,我会简要地解释一下。
拿一个没有循环的小程序来举例。
{ int a=1;
print("%d",a);
}
这个程序的执行时间可以忽略不计。假设声明和打印都只需要一定的时间,那么它的时间复杂度将是O(1)。
另一个程序有一个循环,运行n次。
{int a,i;
long n=10000000;
for(i=0;i<n;i++)
// doing some calculations
}
如您在这里看到的,声明将需要可以忽略不计的时间,即O(1)。如果我们让第4行需要一些时间单位,即O(n),那么总体时间复杂度将是
O(1)+O(n)=O(n).
我不确定你是指大O还是小o,但我的回答会更普遍。
对于内存和时间来说,它的意思是相同的。如果一个函数在内存中增长为O(1),那么它使用恒定数量的内存,而不管输入大小。如果一个函数以O(n)增长,则使用线性数量,如果是O(n*n),则使用二次方数量。