两个线性嵌套循环的Big-theta运行时，内部循环的运行次数是外部循环每次迭代的一半。

Question

我在这个算法问题上遇到了很多麻烦。我应该找到以下算法的big-theta分析：

function example(n):
    int j=n
    for i=0;i<n;i++:
        doSomethingA()
        for k=0;k<=j;k++:
            doSomethingB()
        j/=2

我的方法是将算法的整个执行过程分成两部分。其中doSomethingA()和doSomethingB()都被调用的一部分，j之后的第二部分变为0，只有doSomethingA()被调用，直到程序暂停。

使用这种方法，第一部分出现在外部循环的Logn迭代中，第二部分出现在外部循环的n-logn迭代中。

每次内循环运行的次数减半，因此它运行的总次数应该是2n-1。因此，第1部分的运行时应该是(2n-1)*c，一个常量。我不完全确定这是不是真的

对于第2部分，循环内的工作始终是恒定的，并且循环重复(n-logn)次。

所以我们有((2n-1)+(n-logn))*c

我不确定到目前为止我所做的工作是否正确，也不确定如何继续下去。我的直觉告诉我这是O(n)，但我不确定如何在big-theta中将其合理化。除此之外，我的整个方法都可能是有缺陷的。我该如何回答这样的问题呢？如果我的方法是有效的，我应该如何完成它？

谢谢。

Answer 1

更容易调查doSomethingA和doSomethingB的执行频率。

对于doSomethingA来说，这显然是n次。

对于doSomethingB，我们得到(n+1) + ( n /2+1) + (n/4+1) + ... +1，因此大致为2n +n。n+n/2+n/4+…N是1的总和。

总而言之，我们得到O(n)和Theta(n)，因为你至少需要Omega(n)，从doSomethingA被执行的n次可以看出。