함수는 배열, 배열 길이 및 배열의 연속 요소 수를받습니다. 배열을 실행하고 '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);
}
복잡성 분석의 요점은 알고리즘이 사용하는 시간 (시간 복잡성), 스토리지 (스토리지 복잡성) 또는 메모리 (메모리 복잡성)를 크게 파악하는 것입니다. 이를 위해 우리는 (무한하게) 큰 차원에 대해 생각하는 경향이 있습니다. 왜냐하면 차원이 매우 작 으면 너무 많이 신경 쓰지 않는 경향이 있기 때문입니다. 알고리즘은 요소 수와 연속 요소 수에 따라 다릅니다.
(무한) 많은 요소가 있다고 가정하면 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)이므로 기본적으로 선형 알고리즘이 있습니다.
이 기사는 인터넷에서 수집됩니다. 재 인쇄 할 때 출처를 알려주십시오.
침해가 발생한 경우 연락 주시기 바랍니다[email protected] 삭제
몇 마디 만하겠습니다