算法分析

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)和(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。

这作为对循环之和的评估是正确的吗？

三重求和我认为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(无穷大)，因为if语句中存在无限递归，假设它是真的，这将是最坏的情况。虽然，对于纯分析，我分析了这是否为真，并且if语句将不会运行。由于以下原因，我得到了O(nk)的复杂性：

1的和(k=0到3000)和(j=0到nk)，然后计算为nk( 3001 ) +3001。因此是O(nk)，其中k不被丢弃，因为它控制循环的迭代次数。

Answer 1

编号1

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

为了找到复杂性，我们想要找到内环被评估的次数。如果求和从1到n，通常很容易求解，所以我将在后面将0从0去掉。如果我是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。中间循环基于i的当前值运行，因此我们需要做一个求和：

​

​

中间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

对于最后一个，它实际上是O(无穷大)，如果a< 12，因为if语句。从技术上讲，一切都是O(无穷大)，因为Big-O只提供了运行时的上限。如果a< 12，它也是omega(无穷大)和θ(无穷大)。如果只运行其余部分，那么我们将得到从i*n的1到2999之间的求和：

​

​

注意，从1到2999的求和是一个常数(它是4498500)，这一点非常重要。不管一个常数有多大，它仍然是一个常数，不依赖于n。我们最终会把它抛出运行时计算之外。有时，当一个理论上快速的算法有一个大常数时，它实际上比理论上慢的其他算法要慢。我能想到的一个例子是Chazelle线性时间三角剖分算法。从来没有人实施过它。无论如何，我们有4498500 * n，这是θ(N)：

​

​