코드 조각의 Big-O 복잡성

코드 조각의 Big-O 복잡성

---

복잡성에 대한 알고리즘 설계에 대한 질문이 있습니다. 이 질문에서 코드 조각이 주어지고이 코드의 복잡성을 계산해야합니다. 의사 코드는 다음과 같습니다.

for(i=1;i<=n;i++){
    j=i
    do{
        k=j;
        j = j / 2;
    }while(k is even);
}

몇 가지 숫자에 대해이 알고리즘을 시도했습니다. 그리고 나는 다른 결과를 얻었습니다. 예를 들어 n = 6이면이 알고리즘 출력은 다음과 같습니다.

i = 1 -> executes 1 time
i = 2 -> executes 2 times
i = 3 -> executes 1 time
i = 4 -> executes 3 times
i = 5 -> executes 1 time
i = 6 -> executes 2 times

일반 테마가 없는데 어떻게 계산하면 되나요?

---

다른 답변에 의해 주어진 상한이 실제로 너무 높습니다. 이 알고리즘에는 O (n) 런타임이 있으며 이는 O (n * logn)보다 더 엄격한 상한입니다.

증명 : 내부 루프가 수행 할 총 반복 횟수를 계산해 봅시다.

외부 루프는 n시간을 실행 합니다. 내부 루프는 각각에 대해 적어도 한 번 실행됩니다.

• even i의 경우 내부 루프가 적어도 두 번 실행됩니다. 이것은 여러 n/2번 발생합니다 .
• 들어 i4로 나누어, 내부 루프는 적어도 세 번 실행됩니다. 이것은 여러 n/4번 발생합니다 .
• 들어 i8로 나누어, 내부 루프는 4 회 이상을 실행합니다. 이것은 여러 n/8번 발생합니다 .
• ...

따라서 내부 루프가 실행되는 총 횟수는 다음과 같습니다.

n + n/2 + n/4 + n/8 + n/16 + ... <= 2n

내부 루프 반복의 총량 사이 n및 2n, 즉 그것의 Θ (N).

---

당신은 항상 각 레벨에서 최악의 시나리오를 얻는다고 가정합니다.
이제 N 개의 요소가있는 배열을 반복하므로 O(N)이미 시작 합니다.
지금의 당신의 말을하자 i항상 같음 X과 X(기억, 최악의 경우마다)도 항상.
얼마나 많은 시간을 당신은 분열에 필요 X에 의해 2얻을 1? (짝수가 1에 도달하면 나눗셈을 중지하는 유일한 조건입니다).
즉, 우리는 방정식 해결해야 할 X/2^k = 1것입니다 X=2^k그리고 k=log<2>(X)이것은 우리의 알고리즘 걸릴 수 있습니다 O(n log<2>(X))easly으로 기록 할 수있는 단계를,O(nlog(n))

---

이러한 루프의 경우 내부 루프와 외부 루프의 개수를 분리 할 수 ​​없습니다.

따라서 우리는 모든 단계를 세어야합니다.

사실, 외부 루프의 각 반복 (on i)에 대해

1 + v_2(i) steps

의 소인수 분해 의 검정력에 해당하는 v_22-adic 평가 (예 : http://planetmath.org/padicvaluation 참조)는 어디에 있습니까 ?2i

따라서 모든 단계를 추가 i하면 총 단계 수는 다음과 같습니다.

n_steps = \sum_{i=1}^{n} (1 + v_2(i)) 
        = n + v_2(n!)    // since v_2(i) + v_2(j) = v_2(i*j)
        = 2n - s_2(n)    // from Legendre formula (see http://en.wikipedia.org/wiki/Legendre%27s_formula with `p = 2`)

우리는 다음 볼 단계의 수 입니다 정확히 :

n_steps = 2n - s_2(n)

대로 s_2(n)의 숫자의 합이다 n자료는 2, 그것이 무시할 (기껏 log_2(n)베이스에 자리 이후 20 또는 1이고, 가장 거기 같이 log_2(n)비교 자리) n.

따라서 알고리즘의 복잡성은 다음과 같습니다 n.

n_steps = O(n)

이는되어 있지O(nlog(n)) 다른 많은 솔루션을하지만 작은 수량에 명시된!

---

최악의 경우부터 시작하겠습니다.

2 (적분)로 계속 나누면 1에 도달 할 때까지 멈출 필요가 없습니다. 기본적으로 단계 수를 비트 폭에 따라 결정합니다. 이는 2의 로그를 사용하여 알아 낸 것입니다. 그래서 안쪽 부분은 lg n입니다. 바깥 부분은 분명히 n이므로 N log N전체입니다.

---

do루프 반쪽 j까지 k홀수된다. k초기의 복사 j사본 인 i그래서, do1 명 + 전원 실행 2나누어진다 i:

• i = 1은 홀수이므로 1 회 통과 do루프를 만듭니다 .
• i = 2는 2로 한 번 나눕니다. 따라서 1 + 1,
• i = 4는 2로 두 번 나눕니다. 따라서 1 + 2 등입니다.

That makes at most 1+log(i) do executions (logarithm with base 2).

The for loop iterates i from 1 through n, so the upper bound is n times (1+log n), which is O(n log n).

ReferenceURL : https://stackoverflow.com/questions/30233242/big-o-complexity-of-a-piece-of-code