algorithm - 两个线性嵌套循环的 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() 直到程序停止。

使用这种方法，第 1 部分发生在外循环的 Logn 次迭代中，第 2 部分发生在外循环的 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+... 的 2n 和来自对 1 求和的 n。

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