Linux伊甸园论坛 » Java/XML专版 » 【求助】算法分析

benny_toto 发表于 2006-6-3 16:49

【求助】算法分析

[color=black][font=CourierNewPSMT][font=Times New Roman]function mystery(x, y)[/font][/font][/color]

[color=black][font=CourierNewPSMT][font=Times New Roman]z := 1[/font][/font][/color]

[color=black][font=CourierNewPSMT][font=Times New Roman]while (y != 0){[/font][/font][/color]
[color=black][font=CourierNewPSMT][font=Times New Roman]          if (y % 2 = 0){[/font][/font][/color]
                [color=black][font=CourierNewPSMT][font=Times New Roman]x = x * x[/font][/font][/color]
               [color=black][font=CourierNewPSMT][font=Times New Roman]y = y / 2[/font][/font][/color]
[font=Times New Roman]             }[/font]

[color=black][font=CourierNewPSMT][font=Times New Roman]          else{[/font][/font][/color]
               [color=black][font=CourierNewPSMT][font=Times New Roman]z = z * x[/font][/font][/color]
               [font=Times New Roman][color=black][font=CourierNewPSMT]y = y - 1[/font][/color][i][color=#4e0000][/color][/i][/font]
         }
}
[color=black][font=CourierNewPSMT][font=Times New Roman]return z;[/font][/font][/color][color=black][/color]

请教大家一下,这个算法的complexity是O(log n) 还是 O(n), 还是别的..请详细说明一下为什么,
谢谢。......

fogs123x 发表于 2006-6-3 19:52

不知道楼主到底要得到的是什么?

我就说下这个程序的执行好了:

在while循环这里,如果y的值不等于0,那么将一直进行下面的循环.

之后是if,如果y与上2等于0,那么将执行if语句中的代码,那么便是x=x*x,y=y/2.,之后再跳到while循环,直到while循环中的条件成立,再退出循环,最后返回一个变量z的值,这时z
应该为1.

如果if语句中的判断不成立,那么执行else中的语句z=z*x,y=z-1,之后再跳到while循环,直到while循环中的条件成立,再退出循环,执行return语句,返回一个z变量的值.这时z变量的值则是else语句中算出的那个值.

zhuomingliang 发表于 2006-6-5 14:19

回楼上，楼主是要得到这个函数的时间复杂度。
应该是O(log n)

下列算法也是O(log n)
for(i=1;j<=n;i=2*i)
   count<<"i="<<i;

fogs123x 发表于 2006-6-5 16:24

count?
好象是cout吧,那不是C++里面的东西,为撒会在我的Java版出现~~~晕

zhuomingliang 发表于 2006-6-6 10:08

不好意思，错了～～，是cout
因为我忘记了java的语法，最近又常用c++，所以写出c＋＋的了

wangyi160 发表于 2006-6-22 16:45

很简单啊，是O(logn).
肯定是把y看成n拉，想一下，至多操作２次使Ｎ变成Ｎ／２，所以
Ｔ（Ｎ）＜＝Ｔ（Ｎ／２）＋２
这样就很明显拉

LinuxFanTgh 发表于 2006-7-14 21:10

楼上正解，高手阿

查看完整版本: 【求助】算法分析