给定长度的数组，寻找最大数

hbmhalley

若复杂度O(f(n))低于O(n)，对任意常数c，必存在N，使任意n>N，c*f(n)<n
任意n个数，用O(f(n))算法解，由于c*f(n)<n，必有一数未考虑到；将此数更新为最大值，不影响原算法过程，导致答案错误。

cokeboL

回复 10# hellioncu


我没概念。。。

线性的都叫O(n)?

hbmhalley

回复 12# cokeboL


    那么证不靠谱 ..

    比如
    O(1)=O(1)
    O(k+1)=O(k)+O(1)=2*O(1)=O(1)
    归纳得 O(n) = O(1)
    显然不靠谱

cokeboL

回复 13# hbmhalley


    文科生，不懂那么多，就记得高中学过一个什么数学归纳法，我想表达的是那个意思~而且用的不是*，用的+

hellioncu

cokeboL 发表于 2013-01-11 14:17
回复 10# hellioncu

我也不是很懂。
对于复杂度，n加减乘除一个常数，都是n

cokeboL

这个应该推不出来吧？

1. O(k+1)=O(k)+O(1)=2*O(1)=O(1)

复制代码

cokeboL

回复 15# hellioncu


    俺文科，大学没学过计算机语言，半路出家，版大见笑~

hbmhalley

回复 16# cokeboL


    O(k+1)=O(k)+O(1)没问题
    2*O(1)=O(1)也没问题
    但O()是带着常数的
    如果要用O()表示复杂度，这个常数是不能依赖 n 的
    但归纳的过程中，这个常数是在随着n增长的
    在n确定的情况下是常数，但没有n的时候这不是个常数
    所以依赖规模 n 的归纳是错的

cokeboL

回复 18# hbmhalley


   

hellioncu

cokeboL 发表于 2013-01-11 14:26
回复 15# hellioncu

俺也不是科班出身