求助，分析一个算法的运行时间

[20015jjw]

有个算法，输入是一个长度为 n 的 list

有 50%的几率，这个算法走一遍 list 就能 return ，那用时就是 O (n )
还有 50%的几率，这个算法走一遍，先会走一遍 list ，然后把 list 切成 1/3 长，然后递归地继续跑这个 1/3 长的 list ，然后这个用时是啥...

然后我就不知道怎么分析这个算法的总体时间了...
求学过算法的指点 qwq

[yxjxx]

算法导论 主方法

[c742435]

貌似还是 O (n )

[c742435]

我数学特别烂，但我知道如果把你的问题中的 1/3 换成 1/2.然后用时就是 1/2 + 1/4 + 1/8......，结果等于 2 ，是一个常数。所以你问题的用时倍数肯定也是一个常数 而且小于 2 。
而时间复杂度乘以一个常数是不变的。

[Valyrian]

假设算法的时间是 f (n )
那么 E (f (n )) = 0.5 * O (n ) + 0.5 * (O (n ) + E (f (1/3n ))) = O (n ) + 0.5 * E (f (1/3 n ))
根据 master theorem ， E (f (n )) = O (n )

[wbingeek]

算法导论公开课这一集看： http://open.163.com/movie/2010/12/2/E/M6UTT5U0I_M6V2T4T2E.html

[hitmanx]

”还有 50%的几率，这个算法走一遍，先会走一遍 list ，然后把 list 切成 1/3 长，然后递归地继续跑这个 1/3 长的 list ，然后这个用时是啥...“

把 list 切成 1/3 长后，是要处理 3 个"1/3"长的，还是只处理其中一个？如果是 3 个都要处理的话，这就是归并排序吧， O (nlgn )。如果只处理其中一个的话，那是 O (n )。不知道有没有算错

[wshcdr]

你这个应该还是 O (n )