heapify方式添加数组的复杂度问题

Question

data = new Array<>();
for (int i = parent(arr.length - 1); i >= 0 ; i--) {
        siftDown(i);
}

第一个问题，data = new Array<>();其实这也是个O(n)级别的操作吧？这个问题波波老师没有在视频中提到，是因为这个操作不会对整体复杂度分析带来影响吗？

然后对近乎一半的数据进行下沉操作，这个操作上面的问题中已经给出答案，是O(n)级别的操作；

第二个问题，因为两个操作没有互相嵌套，只是并行。所以可以理解为O(2n)既是O(n)级别是吧？

因为是从别的专业转入计算机行业的，大学对这方面了解甚少。对复杂度分析算是初级小菜鸟，望波波老师指导。

Answer 1

liuyubobobo 2018-10-26 02:56:54

赞思考！

你的第一个问题极其深刻。其实已经脱离了算法与数据结构的问题框架，属于编译，操作系统层面的问题了：）简单地说，我们可以近似的认为，一次开辟空间操作（一次new操作），是一个O(1)级别的操作。具体，我要开辟一个空间（或者对于静态数组来说，是一片连续的空间），操作系统是如何找到这片空间的，内部有很多机制，整体，这些机制保证了这个操作速度不是O(n)的，而是O(1)的（是近似）。

或者，你可以这么理解。算法复杂度分析本身就是一个理论层面的内容。所以我们考虑的是在外在条件不影响算法的情况，即不会出现系统内存不足，找了半天都没找到可用的内存以完成这个new操作的情况下，算法的性能。所以，我们在分析复杂度的时候，每次new，都看作是操作系统提供的一个常数级操作。

具体，操作系统是如何找到连续可用的内存，如何分配内存，找不到可用的内存如何处理，等等等等，这些问题，都是操作系统领域的问题了：）

所以，对于你的第二个问题，本质上不存在。但你的思考很好。假设有这样一个算法，包含两个互不嵌套的O(n)循环：

for(int i = 1; i < n; i ++)
    ;// 做一些O(1)级别的操做
for(int i = 1; i < n; i ++)
    ;// 再做一些O(1)级别的操作

这个算法的时间复杂度是O(n)的。和你分析的一样。你可以写成O(2n)，但在大O表示法中，系数，常数，低阶项，统统没有意义。所以：O(2n) = O(n)。大O表示的是渐进复杂度，描述的是n趋于无穷时的情况：）

最后，值得一提的是：前面我虽然说我们的大多数算法不考虑外在的设备条件。但也确实有一些算法或数据结构，是建立在对外在设备运行机制的考量基础上的。最典型的，B类树就是其中的一种。不过这已经超出这个课程的范畴了。有兴趣的话，在学习完这个课程后，可以寻找更多资料进行自学：）

转专业不易，敢转专业的人都值得敬佩。

加油！：）

• 提问者 PerryMore #1

  谢谢波波老师！