究竟如何才算是o(n)时间？
我现在有些搞不明白了
打个比方
一个数组8个元素 将其排序要求在o(n)时间内解出
只是打个比方
按照起泡排序
需要o(n^2)
然后 如果for(i = 1; i <=8; i++)
这样算是线性? 应该是因为1-8每个元素只便利了一遍
看下面
for(i = 1; i<=8; i++)
;
for(i = 1;i <= 8; i++)
;
也就是说1-8我循环了2次
这种也属于o(n)时间内？？还是o(2n)?
如果是o(2n)我就搞不明白了
因为最近在做一道题 输油管道问题
里面的关键所在 就是求一些数的中位数
比如说 1-8个元素 排好序之后 求之中的 中间那个数
通俗点说就是N个数求第K小的数是那一个
我看了百度上的很多回答 都说这种解法 利用快速排序法
便可以在o(n)时间内完成
我仔细想想不对啊 1趟快排已经用了o(n)次 更何况1趟快排 不可能得到第K小的元素
所以我现在有些搞不明白了 究竟怎样才算是o(n)??
[解决办法]
O(2n) 就是 O(n) 因为O里隐含了系数K
N个数求第K小的数
那个貌似是叫 nth-element 的吧
只是利用了快排的思想 并不是排序好了再取的
[解决办法]
最高次数是n的一次方就叫O(n)
n叫O(n),n/2叫 O(n),100*n+50 也叫O(n)
[解决办法]
由幂来确定，和系数无关，和常数无关
[解决办法]
大O表达式时间复杂度n的系数不用给出100000*n复杂度也算O(n)。关键是问题复杂度规模。可以考虑桶排序。
[解决办法]
