最近我发现了这段 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)。
最佳答案
它是 O(n)
因为您有 for 循环运行 n
次而 while 循环可以在 if
中替换> 声明。 start
从 0 开始,除
start++;
在循环中。这意味着您将在 while
循环中执行最多 n
次
关于algorithm - SubArray 的运行时间等于一个总和,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/18820573/