알고리즘 분석 : Big Oh Complexity, 함수로 표현 출력

Question

다음 함수에서 반환되는 값은 무엇입니까? 답을 n의 함수로 표현하십시오. 최악의 경우 실행 시간을 O() 표기법으로 지정하십시오. 알고리즘

은 의사 코드 :

F1(n) 

    v = 0 

    for i = 1 to n 
     for j = n + 1 to 2n 
      v++ 
    return v 

내 접근법 :

F1 (N)의 출력시에 대한 루프 내에서 계산 된 변수 V로부터 반환 된 정수 값 반복 크기는 2n이고 외부 for 루프의 크기는 n입니다.

변수 v는 두 루프의 반복이 시작되기 전에 0으로 초기화됩니다. i 번째 for-loop가 첫 번째 i 번째 iteration에있을 때 j 번째 for-loop (inner for-loop)는 크기 n + 1에서 2n으로 반복됩니다. n = 5, j 번째 for-loop가 j = 6에서 10으로 반복한다고 가정하면, 이것은 v가 내부 for-loop의 전체 반복에 대해 증가 된 횟수를 의미합니다.

j 번째 for-loop는 항상 v를 n-1 (이 경우 4)만큼 증가시키기 때문에 각 전체 반복에서 i 번째 for 루프가 1에서 n으로 시작하면 변수 v가 ​​n- 매 반복마다 1 번.

그래서이 알고리즘은 함수 g (n) = (n-1) * (n-1)을 매핑합니다. 어느 것이 4 * 4가 될 것이므로 n = 5 일 때 v = 16이됩니다. 이것은 n = 5 일 때 모든 전체 jth 반복 v가 4 씩 증가하기 때문에 사실입니다. i 번째 for-loop가 i = 1, ..., 4 (1 ~ n) 그러면 v가 i가 증가 할 때마다 4 씩 증가하여 결과가 (n-1 * n-1) 인 이유를 설명합니다.

외부 루프가 1 번에서 n 번 반복되고 내부 루프가 n + 1에서 2n 번 반복되는 중첩 루프 구조를 갖고 있기 때문에이 프로그램의 최악의 경우 Big O 복잡도는 O (n^2)입니다. 또한 n의 모든 값을 반복하므로 n 번에 해당합니다.

마지막으로, 변수의 초기화/증가에는 O (1) 시간이 필요하므로 중첩 된 for-loop와 비교할 때 복잡성에 많은 영향을 미치지 않습니다.

Answer 1

나에게이 코드는 [1,n] 범위의 모든 값을 계산하면 루프 for i=1 to n이 n 번 실행되기 때문에 g(n)=n^2 함수를 매핑합니다. 물론 그것이 [1,n) 인 경우 g(n)=(n-1)^2이 있지만 대회의 문제입니다.

두 개의 중첩 루프는 각각 n 번 실행되어 O(n^2)의 복잡도를 제공합니다.이 경우 가장 좋음 - 최악입니다. 그래서 당신의 접근 방식이 괜찮 으면 질문 :