第一个循环运行O(log )时间,但第二个循环的运行时间取决于第一个循环的计数器,如果我们进一步检查它,它应该像(1+2+4+8+16....+N)一样运行,我就是找不到这个系列的合理答案…… for (int i = 1; i < n; i = i * 2) for (int j = 1; j < i; j++)
{
对于这个伪码,什么是大O: if n=1 then return BinarySum(A, i, n/2) + BinarySum(A, i+[n/2], [n/2])这非常令人困惑,因为我认为这是O(logn),因为每次运行函数时,都会被除以2,但是有些人认为它是O(n),而不是O(logn),因为算法通过