我对O（n）在空间中的含义有很高的理解。这意味着对于具有输入 n 的算法，该算法分配的额外内存存储将按比例增加到 n。
因此，如果您有一个算法，该算法将数字 n 作为输入，并创建一个大小为 2n 的数组并将其全部填充为 0，则时间复杂度将为 O（n），空间复杂度将为 O（n），因为您正在创建一个相对于输入大小的数组（附加存储）。这种理解正确吗？
其次，O（n）的空间复杂度有多糟糕？像快速排序这样的流行排序算法在最坏情况下的空间复杂度为 O（n），那么对于任意长的数据进行排序，O（n） 空间复杂度是否有可能产生可怕的影响？如果是这样，是否有任何关于为什么或如何的直觉？
大 O 表示法中的 N 通常表示输入的大小，而不是传递给算法的值。
O（n） 的空间复杂度意味着对于每个输入元素，最多可以分配固定数量的 k 字节，即运行算法所需的内存量在 k*N 处的增长速度不超过线性增长。
例如，如果排序算法分配一个由 N/2 个元素组成的临时数组，则称该算法具有 O（n） 空间复杂度。
没有一些上下文，就不可能说它是好是坏。在许多情况下，O（N） 的空间复杂度是可以接受的，但该规则也有例外。有时，您增加内存复杂性以降低时间复杂性（即为显着的加速付费内存）。这几乎被普遍认为是一个很好的权衡。
O（n） 表示成本随输入元素数量的增加而增加，速率是线性的，而不是指数的（例如 O（n^2））或对数的（例如 O（log（2））），在这些情况下，例如键表中的元素数量。如果你需要你的算法有效地处理n的大值，特别是如果你有一个替代方法，你可以使用一个小于线性比例的替代方法（例如O（log（n））），那么O（n）是不好的。
时间复杂度和空间复杂度是不同的问题。
空间复杂性只是一个大问题，如果对于 n 的可能值，您最终将使用有问题的内存或存储量。在许多情况下，存储的 O（n） 可能是预期的，因为为了在某些事情上实现小于 O（n），您需要压缩数据，和/或您的数据可能有重复项。举一个基本的例子，如果你有一个键/值函数，其中值很大但经常重复，那么复制每个键的值（即 O（n））可能效率低下，因此存储在映射而不是数组中可能更有效的空间。
在索引查找算法的情况下，通常说最坏情况O（n）是坏的时间复杂度，因为O（n）意味着您可能必须查看索引中的每个元素才能找到您要查找的元素。 也就是说，该算法并不比浏览整个列表直到找到匹配项好多少。与各种长期已知的树索引结构相比，它的效率低下，这些结构确实需要 O（n） 时间 - 也就是说，查找某些内容的时间不会与索引中的元素数量成线性比例地增加，因为树结构减少了所需的比较次数到指数变浅的曲线。
一些其他类型的算法可能没有比O（n）更好的已知解决方案，例如AI代理的字段，它们都可能相互交互。