이 알고리즘의 최악의 분석을 계산하는 방법은 무엇입니까? 내가 이해에서

Question

sum = 0; 
for(int i = 0; i < N; i++) 
    for(int j = i; j >= 0; j--) 
     sum++; 

는, 첫 번째 줄 (1) 작업입니다, 2 라인 3 라인은 (i-1) 운영하고, 4 라인은 n 작업입니다, (i+1) 작업입니다. 이것은 실행 시간이 1 + (i+1)(i-1) + n 일 것을 의미합니까? 나를 혼란스럽게하는 것은이 마지막 단계 일뿐입니다.

Answer 1

알고리즘을 분석하려면 "이 특정 줄에 얼마나 많은 시간이 소요됩니까?"라는 질문을 한 줄씩 건너 뛰고 싶지는 않습니다. 그 이유는 각 행이 동일한 횟수만큼 실행되지 않기 때문입니다. 예를 들어, 가장 안쪽에있는 행은 한 번 실행되는 첫 번째 행에 비해 한 번에 여러 번 실행됩니다.

이와 같은 알고리즘을 분석하려면 알고리즘의 총 런타임의 일정한 인수 내에 값이있는 수량을 확인하십시오. 이 경우, 그 수량은 아마도 "sum++ 라인이 몇 번 실행됩니까?"라고 할 수 있습니다. 왜냐하면이 값을 알면 알고리즘의 두 루프가 소비 한 총 시간을 알 수 있기 때문입니다. 이것을 파악하기 위해 이러한 루프에서 어떤 일이 일어나는지 추적 해 봅시다. 외부 루프의 첫 번째 반복에서는 i == 0이므로 내부 루프는 정확히 한 번 실행됩니다 (0에서 0까지 카운트 다운). 외부 루프의 두 번째 반복에서 i == 1과 내부 루프가 정확히 두 번 실행됩니다 (처음에는 j == 0을 사용하여 j == 1). 일반적으로 외부 루프의 k 번째 반복에서 내부 루프는 k + 1 번을 실행합니다. 가장 안쪽 루프의 반복 횟수가

1 + 2 + 3 + ... + N 

주어진다이 수량이 두 용어

N (N + 1)  N^2 + N N^2 N 
--------- = ------- = --- + --- 
    2    2  2  2 

동일하게 표시 할 수 있고, N^2/2 용어는 지배적 인 성장 기간이고, 그렇다면 우리는 그것의 상수 fa를 무시합니다. 우리는 O (N)의 런타임을 얻습니다.

이 답을 암기해야하는 것으로 보지 마십시오. 답을 얻는 데 필요한 모든 단계를 생각하십시오. 카운트 할 수량을 찾은 다음, 루프의 실행에 의해 그 수량이 어떻게 영향을 받는지를 보았습니다. 이로부터 우리는 그 양에 대한 수학적 표현을 도출 할 수 있었고, 우리는이를 단순화했습니다. 마지막으로, 결과 표현식을 취하여 전체적인 기능에 대해 큰 역할을하는 지배적 인 용어를 결정했습니다.

Answer 2

추가되지 않습니다. 내부 루프는 외부 루프의 각 반복에 대해 한 번 발생합니다. O (n)입니다.

그런데 이것은 우리가 이런 종류의 일에 대해 점근 표기법을 사용하는 이유의 좋은 예입니다. "연산"의 정의에 따라 수의 정확한 세부 사항이 매우 다양 할 수 있습니다. (마찬가지로, sum++은 단일 작업입니까, 아니면 add sum to 1 giving temp; load temp to sum입니까?) 그러나 우리는 상수 요소에 숨길 수있는 모든 것을 알고 있으므로 O (n)가 될 것입니다.

Answer 3

아니오; 각 행에 대해 특정 수의 작업을 계산하지 않고 추가합니다. 'for'와 같은 구조의 전체적인 점은 주어진 코드 행이 두 번 이상 실행될 수있게하는 것입니다. 당신은 생각과 논리 기술을 사용하여 'sum ++'라인이 몇 번이나 실행되는지를 N.Hint의 함수로 파악해야합니다. 세 번째 라인이 발생할 때마다 한 번씩 실행됩니다.

두 번째 줄은 몇 번입니까?

두 번째 줄에이 발생할 때마다 'i'값이 설정됩니다. 세 번째 라인은 그 숫자가 인 을 몇 번이나 실행합니까? 따라서 전체적으로 몇 번이나 실행됩니까? (힌트 : 여러 번 다른 금액으로 돈을 줄 경우, 내가 준 총 금액은 어떻게 알 수 있습니까?)

세 번째 줄이 나올 때마다 네 번째 줄이 한 번 발생합니다.

어떤 라인이 가장 자주 발생합니까? N의 관점에서 얼마나 자주 발생합니까?

Answer 4

내부에서 작업.

sum++ 

이것은 반복하지 않기 때문에 이것은 하나의 작업입니다.

for(int j = i; j >= 0; j--) 

이 루프는 i + 1 회 반복됩니다. 거기에 몇 가지 작업이 있지만 아마도 asm 명령의 수를 세는 것을 의미하지는 않습니다. 그래서 저는이 질문에 대해 i + 1의 배수라고 가정 할 것입니다. 루프 내용은 단일 작업이기 때문에 루프와 블록은 i + 1 작업을 수행합니다.

이것은 N 번 반복됩니다. 이전과 마찬가지로, 이것은 N의 배수입니다. 블록이 i + 1 연산을 수행하므로이 루프는 총 N (N + 1)/2 연산을 수행합니다. 그리고 그것은 당신의 대답입니다! big-O 복잡성을 고려하려면 O (N)로 단순화하십시오.

Answer 5

그래서 당신이 합계 ++와 얼마나 많은 시간을 당신이 그것을 실행하는지 짐작하십시오.

최종 합계가 그 답을 줄 것입니다.

사실 루프는 다음과 같습니다

시그마 (n)을 n은 1 내지 N의 이동

동일 어떤이 큰 - 오 - 표기법으로 O(N^2)

또한 옆에 당신을 줄 N*(N+1)/2 질문의 이름은 알고리즘에 최악의 경우가 없습니다. 또는 N이 무한대로 갈 때 최악의 경우라고 말할 수 있습니다. 당신의 루프를 표현하기 위해 시그마 표기법을 사용

Answer 6

는 :