你能告诉我我的函数的时间复杂度 (Big-O) 是多少吗？

Question

函数接收一个数组，数组长度和数组的连续元素数。我运行一个数组并寻找 'K' 个连续元素的最大总和

#include <iostream>

using std::cin;
using std::cout;
using std::endl;

int GetLargestSum(int array[], int length, int k)
{
    int largestSum = 0;
    int previousSum = 0;
    for (int i = 0; i <= length - k; i++){
        if (i == 0){
            for (int j = 0; j < k; j++){
                largestSum += array[j];
            }
            previousSum = largestSum;
        } else{
            int currentSum = previousSum - array[i - 1] + array[i + k - 1];
            if (currentSum > largestSum){
                largestSum = currentSum;
            }
            previousSum = currentSum;
        }
    }
    return largestSum;
}

int main(){
    int k = 3;
    int array[] = {1, -3, 4, 1, 7, -5, 9};
    cout << "Largest sum of " << k << " consecutive elements of an array = " << GetLargestSum(array, 7, 3);
}

Answer 1

根据我的理解，代码执行以下操作：

先遍历前K个元素求和
从现在开始，它只会添加下一个传入元素并删除当前元素的第一个元素 window 并检查此总和是否大于或小于当前总和。

所以这样你只遍历数组一次。所以 O(N) （N 是数组的长度）

Answer 2

if (i == 0) ... else ... 是一种混淆的方式，在循环外写同样的东西并在 1:

开始循环

int GetLargestSum(int array[], int length, int k)
{
    int largestSum = 0;
    int previousSum = 0;

    for (int j = 0; j < k; j++){
        largestSum += array[j];
    }
    previousSum = largestSum;

    for (int i = 1; i <= length - k; i++){
        int currentSum = previousSum - array[i - 1] + array[i + k - 1];
        if (currentSum > largestSum){
            largestSum = currentSum;
        }
        previousSum = currentSum;
    }
    return largestSum;
}

现在我们可以删除所有需要常量操作的部分：

int GetLargestSum(int array[], int length, int k)
{
    // init something 

    for (int j = 0; j < k; j++){
        // do something
    }

    // do something

    for (int i = 1; i <= length - k; i++){
        // do something
    }
    return largestSum;
}

我们可以看到复杂度是 O ( max( k, length-k) ) 而 k <= length 这只是 O( length )

Answer 3

不是直接回答而是提示：

如我的评论所述，您可以将内部 for 循环添加到外部。结果如下所示。我还删除了冗余变量 previousSum 并计算了 currentSum 中的初始和。如果 k <= length.

，我的功能应该与您的功能相同

int GetLargestSum(int array[], int length, int k)
{
    int currentSum = 0;
    for (int j = 0; j < k; j++) {
        currentSum += array[j];
    }

    int largestSum = currentSum;
    for (int i = 0; i < length - k; i++) {
        int currentSum += array[i + k] - array[i];
        if (currentSum > largestSum) {
            largestSum = currentSum;
        }
    }
    return largestSum;
}

i 仍然从 0 开始，因为我删除了索引访问中的 - 1 并在 for-condition (< 而不是 <=)。 i 现在始终是下一个从 currentSum 中“删除”的被加数的索引。

Answer 4

分析复杂度的要点主要是找出算法使用了多少时间（时间复杂度），存储（存储复杂度）或内存（内存复杂度）。为此，我们倾向于考虑（无限）大的维度，因为如果维度非常小，我们往往不会太在意它们。您的算法取决于元素的数量和连续元素的数量。

假设有（无限）多个元素，也没有什么能阻止 k 变大。在迭代所有元素的第一步中，但仅在第一步 (!) 中，您执行 O(k) 复杂循环。之后，您继续循环您的元素，并在每个步骤上执行 O(1) 操作，n 次，即 n * O(1) = O(n).

现在，您的时间复杂度为 O(k) + O(n)，由于两者之间没有并行化且没有其他技巧，因此结果为 O(k + n)。由于 k < n，O(k + n) < O(2n) 和 O(2n) = O(n)，基本上你有一个线性算法。

你能告诉我我的函数的时间复杂度 (Big-O) 是多少吗？

Can you tell me what is the time complexity (Big-O) of my function?

c++

arrays

big-o