[java] 계산 복잡도가 왜 O (n ^ 4)입니까?

Program / 글쓴이 
int sum = 0;
for(int i = 1; i < n; i++) {
    for(int j = 1; j < i * i; j++) {
        if(j % i == 0) {
            for(int k = 0; k < j; k++) {
                sum++;
            }
        }
    }
}

j = i, 2i, 3i … 마지막 for루프가 n 번 실행되는 방법을 이해하지 못합니다 . 나는 우리가 그 if진술에 근거하여 어떻게 그 결론에 도달했는지 이해하지 못한다고 생각 합니다.

편집 : 마지막 루프가 mod 연산자를 기반으로 i 번 실행되는 이유를 제외하고 모든 루프의 복잡성을 계산하는 방법을 알고 있습니다. 기본적으로 j % i가 i가 아닌 i * i까지 올라갈 수없는 이유는 무엇입니까?

답변

루프 A, B 및 C에 레이블을 지정합시다.

int sum = 0;
// loop A
for(int i = 1; i < n; i++) {
    // loop B
    for(int j = 1; j < i * i; j++) {
        if(j % i == 0) {
            // loop C
            for(int k = 0; k < j; k++) {
                sum++;
            }
        }
    }
}
  • 루프 A는 O ( n ) 번 반복합니다.
  • 루프 B 는 A 반복마다 O ( i 2 )를 반복 합니다. 이러한 각 반복에 대해 :
    • j % i == 0 O (1) 시간이 소요됩니다.
    • 이 반복의 1 / i 에서 루프 C는 반복 마다 O (1) 작업을 수행하여 j 번 반복합니다. 이후 j는 O이다 ( 전 2 평균)이 단지 1 / 위해 수행 전 루프의 반복 B 평균 비용은 O이다 ( I 2  /  I ) = O ( I ).

이 모든 것을 곱하면 O ( n  ×  i 2  × (1 +  i )) = O ( n  ×  i 3 )가됩니다. 이후 난 평균 O (에 해당 ),이 O (인 N 4 ).

이것의 까다로운 부분은 if조건이 1 / i 의 시간에 불과 하다는 것입니다 .

기본적으로 j % i가 i가 아닌 i * i까지 올라갈 수없는 이유는 무엇입니까?

실제로, j최대 j < i * i뿐만 아니라까지 올라갑니다 j < i. 그러나의 배수 인 j % i == 0경우에만 조건 이 적용됩니다 .ji

의 배수 i범위 내에서가 i, 2*i, 3*i, …, (i-1) * i. 이 중 루프 B 반복 시간 에도 불구하고 루프 i - 1C에 도달 합니다.i - 1i * i - 1

답변

  • 첫 번째 루프는 n반복을 사용합니다.
  • 두 번째 루프는 n*n반복을 사용합니다. i=n그렇다면 그때를 상상해보십시오 j=n*n.
  • 세 번째 루프는 최악의 경우 경계가 지정된 시간 n만 실행되므로 반복을 소비 합니다.iin

따라서, 코드 복잡도는 O (n × n × n × n)이다.

이것이 당신이 이해하는 데 도움이되기를 바랍니다.

답변

다른 모든 대답은 정확합니다. 다음을 수정하고 싶습니다. 내부 k 루프의 실행 감소가 실제 복잡도를 낮추기에 충분했는지 확인하고 싶었습니다 O(n⁴)..

for (int n = 1; n < 363; ++n) {
    int sum = 0;
    for(int i = 1; i < n; ++i) {
        for(int j = 1; j < i * i; ++j) {
            if(j % i == 0) {
                for(int k = 0; k < j; ++k) {
                    sum++;
                }
            }
        }
    }

    long cubic = (long) Math.pow(n, 3);
    long hypCubic = (long) Math.pow(n, 4);
    double relative = (double) (sum / (double) hypCubic);
    System.out.println("n = " + n + ": iterations = " + sum +
            ", n³ = " + cubic + ", n⁴ = " + hypCubic + ", rel = " + relative);
}

이것을 실행 한 후에는 복잡성이 실제로 분명 n⁴합니다. 마지막 출력 행은 다음과 같습니다.

n = 356: iterations = 1989000035, n³ = 45118016, n⁴ = 16062013696, rel = 0.12383254507467704
n = 357: iterations = 2011495675, n³ = 45499293, n⁴ = 16243247601, rel = 0.12383580700180696
n = 358: iterations = 2034181597, n³ = 45882712, n⁴ = 16426010896, rel = 0.12383905075183874
n = 359: iterations = 2057058871, n³ = 46268279, n⁴ = 16610312161, rel = 0.12384227647628734
n = 360: iterations = 2080128570, n³ = 46656000, n⁴ = 16796160000, rel = 0.12384548432498857
n = 361: iterations = 2103391770, n³ = 47045881, n⁴ = 16983563041, rel = 0.12384867444612208
n = 362: iterations = 2126849550, n³ = 47437928, n⁴ = 17172529936, rel = 0.1238518469862343

이것이 보여주는 것은, n⁴이 코드 세그먼트의 실제 와 복잡성 사이의 실제 상대적인 차이는 주위의 값 0.124...(실제 0.125)에 대해 점근 적 요인이라는 것 입니다. 그것이 우리에게 정확한 가치를 제공하지는 않지만 다음과 같이 추론 할 수 있습니다.

시간 복잡도는 기능 / 방법 이 n⁴/8 ~ f(n)있는 곳 f입니다.

  • Big O 표기법에 대한 Wikipedia-page는 ‘Bachmann-Landau 표기법의 가족’표 ~에서 두 피연산자 측의 한계가 동일하다는 것을 나타냅니다. 또는:

    f는 무증상으로 g와 같습니다.

(나는 n = 362합리적인 결과를 얻는 마지막 값 이기 때문에 363을 제외 된 상한으로 선택했습니다 . 그 후 우리는 긴 공간을 초과하고 상대 값은 음수가됩니다.)

kaya3 사용자는 다음을 알아 냈습니다.

그런데 점근 상수는 정확히 1/8 = 0.125입니다. Wolfram Alpha를 통한 정확한 공식은 다음과 같습니다 .

답변

if복잡성을 변경하지 않고 제거 및 모듈로

원래 방법은 다음과 같습니다.

public static long f(int n) {
    int sum = 0;
    for (int i = 1; i < n; i++) {
        for (int j = 1; j < i * i; j++) {
            if (j % i == 0) {
                for (int k = 0; k < j; k++) {
                    sum++;
                }
            }
        }
    }
    return sum;
}

당신이 혼동하는 경우 if와 모듈로, 당신은 단지와 함께, 그들을 멀리 리팩토링 할 수 j에서 직접 점프 i에 2*i에 3*i… :

public static long f2(int n) {
    int sum = 0;
    for (int i = 1; i < n; i++) {
        for (int j = i; j < i * i; j = j + i) {
            for (int k = 0; k < j; k++) {
                sum++;
            }
        }
    }
    return sum;
}

복잡성을 계산하기 쉽도록 중간 j2변수를 도입하여 모든 반복 변수가 각 반복마다 1 씩 증가하도록 할 수 있습니다 .

public static long f3(int n) {
    int sum = 0;
    for (int i = 1; i < n; i++) {
        for (int j2 = 1; j2 < i; j2++) {
            int j = j2 * i;
            for (int k = 0; k < j; k++) {
                sum++;
            }
        }
    }
    return sum;
}

System.out.println이를 확인하기 위해 디버깅 또는 구식을 사용할 수 있습니다i, j, k 하여 각 방법에서 항상 트리플렛이 동일한 지 있습니다.

닫힌 양식 표현

다른 사람들이 언급했듯이 첫 번째 n 정수 의 합이 같다는 사실을 사용할 수 있습니다 n * (n+1) / 2( 삼각 숫자 참조 ). 모든 루프에이 단순화를 사용하면 다음을 얻을 수 있습니다.

public static long f4(int n) {
    return (n - 1) * n * (n - 2) * (3 * n - 1) / 24;
}

분명히 하지 원래의 코드와 같은 복잡하지만 같은 값을 반환한다.

첫 번째 조건을 구글하면, 당신은 알 수 0 0 0 2 11 35 85 175 322 546 870 1320 1925 2717 3731에 나타나는 “첫 번째 종류의 스털링 번호 : S (N + 2, N).” 0시작 부분에 2 개가 추가되었습니다. 그것은 첫 번째 종류sum 의 스털링 번호 임을 의미합니다 s(n, n-2).

답변

처음 두 개의 루프를 살펴 보겠습니다.

첫 번째는 간단합니다 .1에서 n까지 반복됩니다. 두 번째는 더 흥미 롭습니다. 1에서 i 제곱으로갑니다. 몇 가지 예를 보자. 

e.g. n = 4
i = 1
j loops from 1 to 1^2
i = 2
j loops from 1 to 2^2
i = 3
j loops from 1 to 3^2

총합은 i and j loops을가집니다 1^2 + 2^2 + 3^2.
첫 번째 n 제곱의 합에 대한 공식 n * (n+1) * (2n + 1) / 6이 있습니다.O(n^3) .

마지막 k loop으로 0에서 jif까지만 반복 됩니다 j % i == 0. 부터 j1까지 간다 i^2, j % i == 0마찬가지입니다 i시간. i loop반복 이 반복 되기 때문에 n하나 더 추가 할 수 있습니다 O(n).

당신은 그래서 O(n^3)에서 i and j loops다른 O(n)에서 k loop의 그랜드 총O(n^4)

답변