建议分析算法

Question

我最近一直在练习分析算法。我觉得我对分析非递归算法有很好的理解，但我不确定，并且刚刚开始全面理解递归算法。虽然，我还没有正式检查我的方法，我所做的是否确实是正确的

问是否有人可以检查我已经实现和分析的一些算法，看看我的理解是否正确，或者我是否完全偏离了。

此处：

1)

sum = 0;
for (i = 0; i < n; i++){
    for (j = 0; j < i*i; j++){
        if (j % i == 0) {
            for (k = 0; k < j; k++){
                sum++;
            }
        }
    }
}

我对这个的分析是 O(n^5)，原因是： Sum(i = 0 to n)[Sum(j = 0 to i^2)[Sum(k = 0 to j) of 1]] 评估为： (1/2)(n^5/5 + n^4/2 + n^3/3 - n/30) + (1/2)(n^3/3 + n^2/2 + n/6) + (1/2)(n^3/3 + n^2/2 + n/6) + n + 1。因此它是 O(n^5)

作为循环总和的评估是否正确？

三重求和。我假设 if 语句将始终通过最坏情况的复杂性。这是对最坏情况的正确假设吗？

2)

int tonyblair (int n, int a) {
    if (a < 12) {
        for (int i = 0; i < n; i++){
            System.out.println("*");
        }
        tonyblair(n-1, a);
    } else {
        for (int k = 0; k < 3000; k++){
            for (int j = 0; j < nk; j++){
                System.out.println("#");
            }
        }
    }
 }

我对该算法的分析是 O(infinity)，因为如果假设为真，if 语句中的无限递归，这将是最坏的情况。虽然，为了纯粹的分析，我分析了如果这不是真的并且 if 语句不会运行。由于以下原因，我得到了 O(nk) 的复杂性：

Sum(k = 0 to 3000)[Sum(j = 0 to nk) of 1] 然后评估为 nk(3001) + 3001。因此是 O(nk)，其中 k 未被丢弃，因为它控制循环的迭代次数。

Answer 1

1号

我不知道你是怎么推导出你的公式的。通常添加项发生在算法中有多个步骤时，例如预先计算数据然后从数据中查找值。相反，嵌套的 for 循环意味着乘法。此外，对于这段代码来说，最坏的情况也是最好的情况，因为给定 n 的值，最后的总和将是相同的。

为了找到复杂度，我们想要找到内循环被评估的次数。如果从 1 到 n，求和通常很容易解决，所以我稍后会去掉它们中的 0。如果 i 为 0，则中间循环不会运行，如果 j 为 0，则内部循环不会运行。我们可以将代码等价地重写为：

sum = 0;
for (i = 1; i < n; i++)
{
    for (j = 1; j < i*i; j++)
    {
        if (j % i == 0) 
        {
            for (k = 0; k < j; k++)
            {
                sum++;
            }
        }
    }
}

我可以通过强制外循环从 2 开始来让我的生活更艰难，但我不会这样做。外循环现在从 1 到 n-1 运行s。中间根据i的当前值循环运行s，所以需要做求和：

中间的for循环总是走到(i^2 - 1)，j只能被i整除总共(i - 1)次(i, i*2, i*3, . .., i*(i-2), i*(i-1)).有了这个，我们得到：

然后中间循环执行j次。不过，我们求和中的 j 与代码中的 j 不同。求和中的 j 表示每次执行中间循环。每次执行中间循环时，代码中的j都会是(i * (number of executions so far)) = i * (the j in the summation)。因此，我们有：

我们可以将 i 移动到两个求和之间，因为它是内部求和的常数。那么，1到n求和的公式就是众所周知的：n*(n+1)/2。因为我们要 n - 1，所以我们必须减去 n。这给出：

平方和和立方和的求和也是众所周知的。请记住，在这两种情况下我们只求和到 n-1，我们必须记住分别减去 n^3 和 n^2，我们得到：

这显然是n^4。如果我们一直解决它，我们得到：

2号

对于最后一个，由于 if 语句，如果 a < 12 实际上是 O(infinity)。好吧，从技术上讲，一切都是 O(infinity)，因为 Big-O 只提供运行时间的上限。如果 a < 12，它也是 omega(infinity) 和 theta(infinity)。如果只有else运行s，那么我们就有了i*n的1到2999的求和：

请务必注意，从 1 到 2999 的总和是一个常数（即 4498500）。无论一个常数有多大，它仍然是一个常数，与 n 无关。我们最终会将其排除在运行时间计算之外。有时，当一个理论上快的算法有一个大常数时，它实际上比其他理论上慢的算法慢。我能想到的一个例子是Chazelle's linear time triangulation algorithm。从来没有人实施过它。无论如何，我们有 4498500 * n。这是 theta(n):

建议分析算法

Proposed analysis of algorithm

algorithm

recursion

time-complexity

asymptotic-complexity