big-o - 为内存找到大 o 符号是什么意思

Question

我有一个问题，找到算法所需的内存的大o顺序是什么意思？

就像那和big o操作有什么区别？

例如

一个问题问给定以下伪代码，具有初始化的二维数组 A，两个维度的大小为 n：

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

内存的大 o 符号不只是 n^2 并且计算也是 n^2 吗？

score 17 · Accepted Answer

Big-Oh 是关于某事物如何根据其他事物增长（技术上是某事物如何增长的限制）。最常见的介绍性用法是算法根据输入的大小运行的 速度。

没有什么可以说您不能根据输入的大小使用多少内存。

在您的示例中，由于数组中有一个存储桶用于存储i和中的所有内容j，因此空间需求增长为O(i*j)，即O(n^2)

但是，如果您的算法是跟踪最大和，而不是每个数组中每个数字的总和，则运行时复杂度仍然是O(n^2)，而空间复杂度将保持不变，因为算法只需要跟踪当前 i 、电流 j、电流最大值和正在测试的最大值。

score 3 · Accepted Answer

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

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

score 2 · Accepted Answer

是的，您是正确的，上述伪代码的空间和时间复杂度为 n^2。

但是对于下面的代码，空间或内存复杂度为 1，但时间复杂度为 n^2。我通常会在代码中完成分配等，这会给您带来内存复杂性。

对于 i <- 1 到 n 做

   for  j <- 1  to  n-i  do

                    A[0][0]=  i + j

score 1 · Accepted Answer

老实说，我从来没有听说过“内存大 O”，但我可以很容易地猜到它与计算时间的关系很松散——可能只是设置了一个下限。

例如，很容易设计一个使用 n^2 内存和 n^3 计算的算法，但我认为反过来是不可能的 - 你不能在计算上处理具有 n 复杂度的 n^2 数据。

您的算法复杂度为 1/2 * n^ 2，因此 O(n^2)

score 0 · Accepted Answer

如果A给你的算法，那么空间复杂度是 O(1)。迭代现有的 2D 数组并将值写入现有内存位置不会使用额外的内存。

但是，如果算法分配 A，则空间复杂度为 O(n ² )。

无论哪种方式，时间复杂度都是 O(n ² )。

5 回答 5