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

cjaizss

假设：判断大小，取值，写入，单步四则运算均为常数时间
试证：此问题为O(n)问题

接下来想招做算法的，此题作为一个面试题应该可以。
以前我喜欢出的是排序nlogn,发现没人会，降低要求。

群雄逐鹿中原

首先，逐个寻找，很容易实现一个O(n)的方法。
其次，只要证明少于O(n)是不可能的即可。

hellioncu

因为要最大，所以至少与每个比较一次，所以至少是O(n)

liuiang

看了一眼，貌似现在还进不了你们公司~~~~

zylthinking

liuiang 发表于 2013-01-11 13:20
看了一眼，貌似现在还进不了你们公司~~~~

我也进不了， 嗯， 其实楼主也不喜欢俺， 当年和他说要写一个什么NP的帖子， 到现在还么写， 我不小心提醒了两句， 然后楼主恼了。。。。。。。

cjaizss

zylthinking 发表于 2013-01-11 13:25
我也进不了， 嗯， 其实楼主也不喜欢俺， 当年和他说要写一个什么NP的帖子， 到现在还么写， 我不小心提 ...

呵呵，找个时间我有空就写写吧。
没有什么喜欢不喜欢的，z神性格很直，跟我一样，我很喜欢

cokeboL

回复 1# cjaizss


如果元素只有一个，显然是O(1)，即O(n);

如果元素是n(n>1)个，n个数中找最大的复杂度 = (n-1)个数中找到最大再与最后一个元素比较，
假设O(n) = O(n-1) + 1 = O(n-2) + 2 = ... = O(n-(n-1)) + (n-1) = O(1) + n - 1 = n;

cjaizss

cokeboL 发表于 2013-01-11 13:32
回复 1# cjaizss

在证明此之前，你得先证明寻找前n-1的数的最大值的必要性。
其实
对于2n个数
先找前n个数的最大值
再找后n个数的最大值
再比较获得最大值
也是此问题n级别的算法

cokeboL

回复 8# cjaizss


公司又停电了。。。

那俺就换个方向：

1.n==1时，直接返回即可，复杂度明显为O(1);
2.n > 1时，如果数组只读，那么需要临时变量保存上一次比较值，临时变量第一次赋值就是找一个数，复杂度为O(1);
                找到n中的最大，相当于只留一个，即排除(n-1)个数——因为每次比较（不论比较顺序如何）只能排除一个，
                即排除(n-1)个数的复杂度为O(n-1); 整个过程复杂度为O(1+(n-1)) = O(n);
            
                如果数组可写，比如给小朋友写个程序，让他们说几个数字然后返回最大那个数，那么不需要临时变量保存
                结果，即数组只读情况下省略第一步，只排除(n-1)个数，复杂度为O(n-1).

hellioncu

cokeboL 发表于 2013-01-11 14:07
回复 8# cjaizss

似乎你对复杂度O的理解有些问题