O（n）空间复杂性究竟意味着什么，它的效率如何？
我对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（n）是不好的，特别是如果有一个替代方案你可以使用哪个比例小于线性比例（例如O（log（n）））。
时间复杂性和空间复杂性是不同的问题。
如果对于可能的n值，空间复杂性只是一个大问题，你最终会使用有问题的内存或存储量。 O（n）在许多情况下可能是预期的，因为为了达到小于O（n）某些事情，你需要压缩你的数据，和/或你的数据可能有重复。 对于一个基本的例子，如果你有一个key / value函数的值很大但通常是重复的，那么复制每个key的值可能是低效的，这将是O（n），因此存储在一个映射而不是一个数组中可能会更有效率的空间。
O（n）意味着你可能不得不查看索引中的每个元素来找到你正在查找的元素，因此在索引查找算法的情况下经常会说最坏情况O（n）的时间复杂性。 也就是说，在找到匹配之前，算法并不比遍历整个列表好得多。 与各种众所周知的树索引结构相比，效率低下，这种结构确实需要花费O（n）个时间 - 也就是说，查找内容的时间与索引中元素的数量成线性比例，因为树结构减少了需要比较的指数泛浅曲线的数量。
一些其他类型的算法可能没有比O（n）更好的已知解决方案，例如所有可能相互交互的AI代理的字段。
链接地址: http://www.djcxy.com/p/6813.html上一篇: What exactly does O(n) space complexity mean and how inefficient is it?