Bil*_*son 2 sorting algorithm time-complexity space-complexity data-structures
我对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)的空间复杂性是可以接受的,但规则有例外.有时,您会增加内存复杂性以降低时间复杂度(即使用内存支付以获得显着的加速).这几乎被普遍认为是一个很好的权衡.