如何计算这种复杂性？

Question

#include <stdio.h>
#include <stdlib.h>
int max (int A[], int c, int d);

int main (void)
{
    int i = 0;
    int j = 0;
    int A[3] = {-95,52,3};
    int B[3][3];
    for( i = 0; i < 3; i++)
    {
        for(j = 0; j < 3; j++)
        {
            if(j < i)
            {
                B[i][j] = 0;
            }
            else
            {
                B[i][j] = max(A,i,j); 
            }
        }
    }



}

int max(int A[],int c,int d)
{
    int i = 0;
    int j = 0;
    int max = -100;

    for (i=c; i <= d; i++)
    {
        if(max < A[i])
        { 
            max = A[i];
        }
    }
    return max; 
}

我不明白如何计算复杂度。我认为这是在 n^2 中，但我不知道为什么会这样。

此程序采用单个数组并根据 i 到 j 的最大值创建双精度数组。输出正确。

Answer 1

假设 n 指的是 A 数组的大小以及 B 的二维，那么基本上三个嵌套 for 循环，其中之一 "outsourced" 进入 max 函数。

最坏的情况下（当c为0，d为n-1时），每一个都贯穿n个元素

因此你的复杂度是O(n^3)。

Answer 2

因此，您有两个外部 for 循环（i 和 j），每个循环运行超过 n 个元素。如果j<i你只是做一个O(1)操作，但是如果i<=j那么你就都max。此函数有另一个 for 循环，其中运行遍历 j-i+1 个元素。因为我们知道 i 和 j 都受 n 约束，所以最多 n 个元素。

我们可以简单地通过对索引变量求和来分析嵌套的for循环：

因此，该算法的最坏情况复杂度总计为 O(n^3)。

如何计算这种复杂性？

how to compute this complexity?

c

algorithm

time-complexity