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

hbmhalley

回复 19# cokeboL


    ....
    就是说 O(f(n)) 表示的不是具体计算量，而是一句话：
    任意充分大N，O(f(N)) / f(N) 很接近一个常数
    所以对于具体的n, 不能用O()来表示具体计算量

cokeboL

回复 21# hbmhalley


    等有空了补一下基础概念。。。

cjaizss

hellioncu 发表于 2013-01-11 14:13
似乎你对复杂度O的理解有些问题

对于算法导论里的符号，分大O,小O,theta,omiga
但我这里的题目是问题级别，算法导论里似乎没有提到问题级别这个概念。
而计算理论里的符号相对乱一些，所以在此我借用算法导论里的符号

cokeboL

回复 23# cjaizss


    都不懂，我用的私货O表示循环或者计算次数之类。。。

cjaizss

hbmhalley 发表于 2013-01-11 14:15
若复杂度O(f(n))低于O(n)，对任意常数c，必存在N，使任意n>N，c*f(n)

very good
再稍微严格一点，比如给出推论过程(数学分析语言)n足够大的时候一定存在多个没考虑到的数，再整理整理就是本题的证明

folklore

you can't proof it.
if i have n*(n-1) binary-comparting unit. and assume get infomation from any element cost nothing.
i can proof this issue cost 1
or i have a n*(n-1) way comparator, i also proof it cost 1.



or , at last , i just have one 2-way comparator.
and you want to proof 1+1=2 by tell me 1+1=2.
the defination of "max" itself means you must walk throught all members.

cjaizss

folklore 发表于 2013-01-11 15:14
you can't proof it.
if i have n*(n-1) binary-comparting unit. and assume get infomation from any el ...

恩，不错，题目不严谨，我要修改的严谨一点。

fallening_cu

cjaizss 发表于 2013-01-11 13:05
假设：判断大小，取值，写入，单步四则运算均为常数时间
试证：此问题为O(n)问题

并行的话这可以看作 log2(n) 的复杂度，比如用 cuda 来做