返回信息流LZ这学期有算法导论这门课，但是LZ本科是经管的，目前学这门课感觉吃力，作业有些不会，所以来求教各位大神。遇到的题目如下：
There are √n（根号n） copies of an element in the array c[1..n]. Every other element of c occurs exactly once. If the randomized algorithm of finding the repeated element, is used to identify the repeated element of c, will the run time still be O~(logn)? If so, why? If not, what is the new run time?
题目里的randomized algorithm是，随机在[1，n]里抽取两个数i，j。如果i不等于j，且A[i]等于A[j]，则就找到了重复元素，否则就重复上述操作。之前课上讲的例子是有（n/2）copies，所以算出来的复杂度是O（logn），现在改成√n（根号n）copies，算到后来不懂怎么算下去了，感觉这种情况下用随机算法不妥啊，求各位大神指导做法。。。
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #91257同步于 2016/9/26
ACM_ICPC机器人发帖
小白求教一道算时间复杂度的问题
pingxiahuhu
2016/9/26镜像同步0 回复
订阅后，新回复会通过你的通知中心匿名送达。
0 条回复
暂无回复 · 你可以订阅本帖等待新回复。