找到记忆的大符号是什么意思

Question

我有一个问题,找到算法所需的大内存量是什么意思？

就像那个和大o操作之间的区别一样？

例如

一个问题给出了以下伪代码,带有初始化的二维数组A,两个维度的大小为n:

for  i <- 1  to  n  do
       for  j <- 1  to  n-i  do
                        A[i][j]=  i + j

内存的大符号不是n ^ 2,计算也是n ^ 2吗？

Answer 1

Big-Oh是关于某些东西是如何根据其他东西增长的(技术上是对某些东西增长的限制).最常见的用法介绍对于什么是如何快速的算法根据投入的规模运行.

没有什么说你不能有东西要多少内存根据输入的大小使用.

在你的榜样,因为在阵列中的一切都在一个水桶i和j的空间需求增长,因为O(i*j),这是O(n^2)

但是如果你的算法反过来跟踪最大的和,而不是每个数组中每个数字的总和,那么运行时的复杂性仍然是O(n^2)空间复杂度是恒定的,因为算法只需要跟踪当前的i ,当前j,当前最大值和被测试的最大值.

Answer 2

内存的 Big-O 顺序意味着执行算法所需的字节数如何随着处理的元素数量的增加而变化。在您的示例中，我认为 Big-O 阶数是 n 平方，因为数据存储在大小为 nxn 的方阵中。

大 O 运算顺序意味着执行算法所需的计算数量如何随着处理的元素数量的增加而变化。