addFirst(E e)=O(n)是如何计算出来的呢?

Question

视频中没有讲清楚耶

Answer 1

liuyubobobo 2018-07-07 03:01:52

需要先将整个数组中的所有元素后移一位，腾出第一个位置的空间，然后把新的元素放进这个空间。由于数组中的每个元素都要后移一位，所以时间复杂度是O(n)的：）

Answer 2

提问者 ITdoge 2018-07-07 00:14:38

给我的感觉是有for循环了就是O(n),无论for循环中是对输入的数据进行操作,还是对其他元素进行操作.

• liuyubobobo #1

  不完全。for(int i = 0 ; i < n ; i ++) 肯定是O(n)的；for(int i = 0 ; i*i < n ; i ++)是O(sqrt(n))的（判断一个数是否是素数，会用到类似的循环）;for(int i = 0 ; i < n ; i *= 2) 是O(logn)的（我的《算法与数据结构》课程中，自底向上的归并排序会用到类似的循环）。我在《玩转算法面试》课程中《第二章》，特意提到了，计算复杂度，不能单纯的数循环数（虽然在大多数时候ok），关键还是要看执行的操作数和n的关系：）

• 提问者 ITdoge 回复 liuyubobobo #2

  了解,看来时间复杂度还有更多内容!