这个程序为什么时间复杂度是log2n呢 请各位指教
i=1; ①
while (i<=n)
i=i*2; ②
我数学不太好 为什么语句2的时间复杂度是O(log2n)呢 我不知道该怎么分析一个程序是Ο(nlog2n)还是 Ο(nlogn)的 请大家帮忙指教 最好举下例子, 每次分析时间复杂度都很晕 多谢
[解决办法]
你可以算吧,语句2执行时,i值从1,2,4...n,假设次数为k,则 2^(k-1)=n => k=log2n+1,是O(log2n)的复杂度。