algorithm - SubArray 的运行时间等于一个总和

Question

最近我发现了这段 C 代码，用于查找数组中等于和的整数。

int subArraySum(int arr[], int n, int sum)

{

/* Initialize curr_sum as value of first element
   and starting point as 0 */
int curr_sum = arr[0], start = 0, i;

/* Add elements one by one to curr_sum and if the curr_sum exceeds the
   sum, then remove starting element */
for (i = 1; i <= n; i++)
{
    // If curr_sum exceeds the sum, then remove the starting elements
    while (curr_sum > sum && start < i-1)
    {
        curr_sum = curr_sum - arr[start];
        start++;
    }

    // If curr_sum becomes equal to sum, then return true
    if (curr_sum == sum)
    {
        printf ("Sum found between indexes %d and %d", start, i-1);
        return 1;
    }

    // Add this element to curr_sum
    if (i < n)
      curr_sum = curr_sum + arr[i];
}

// If we reach here, then no subarray
printf("No subarray found");
return 0;

}

我的问题是该算法的运行时间为 O(n)，这可以通过计算在最坏情况下对 arr[] 的每个元素执行的操作次数来证明。据我所知，它看起来像一个 O(n^2) 算法。可能是我错过了学习的东西，但任何人都可以解释这是 O(n)，如果这是 O(n)。

Answer 1

它是 O(n) 因为您有 for 循环运行 n 次而 while 循环可以在 if 中替换> 声明。 start 从 0 开始，除

外从未分配过

start++;

在循环中。这意味着您将在 while 循环中执行最多 n 次