이 섹션에서는 반복문, 순서문, 선택문에 대해 Big O를 결정하는 몇 가지 예를 제공합니다.

실시예 1

다음 루프의 시간 복잡도를 고려하세요.

for (int i = 1; i k = k 5;
}

실행을 위한 상수 시간 c입니다.

k = k 5;

루프가 n번 실행되므로 루프의 시간 복잡도는 다음과 같습니다.

T(n) = (상수 c)*n = O(n).

이론적 분석은 알고리즘의 성능을 예측합니다. 이 알고리즘이 어떻게 수행되는지 확인하기 위해 아래 프로그램의 코드를 실행하여 n = 1000000, 10000000, 100000000 및 100000000에 대한 실행 시간을 얻습니다.

우리의 분석은 이 루프의 선형 시간 복잡도를 예측합니다. 샘플 출력에 표시된 것처럼 입력 크기가 10배 증가하면 런타임도 대략 10배 증가합니다. 실행은 예측을 확인합니다.

실시예 2

다음 루프의 시간 복잡도는 얼마입니까?

for (int i = 1; i for (int j = 1; j k = k i j;
}
}

실행을 위한 상수 시간 c입니다.

k = k i j;

외부 루프는 n번 실행됩니다. 외부 루프의 각 반복에 대해 내부 루프는 n번 실행됩니다. 따라서 루프의 시간 복잡도는 다음과 같습니다.

T(n) = (상수 c)*n*n = O(n^2)

O(n^2) 시간 복잡도를 갖는 알고리즘을 2차 알고리즘이라고 하며 2차 증가율을 나타냅니다. 2차 알고리즘은 문제 크기가 증가함에 따라 빠르게 증가합니다. 입력 크기를 두 배로 늘리면 알고리즘 시간은 네 배로 늘어납니다. 중첩 루프가 있는 알고리즘은 종종 2차적입니다.

실시예 3

다음 루프를 고려하세요.

for (int i = 1; i for (int j = 1; j k = k i j;
}
}

외부 루프는 n번 실행됩니다. i = 1, 2, c인 경우 내부 루프는 1회, 2회, n회 실행됩니다. 따라서 루프의 시간 복잡도는 다음과 같습니다.

실시예 4

다음 루프를 고려하세요.

for (int i = 1; i for (int j = 1; j k = k i j;
}
}

내부 루프는 20번 실행되고 외부 루프는 n번 실행됩니다. 따라서 루프의 시간 복잡도는

T(n) = 20*c*n = O(n)

실시예 5

다음 순서를 고려하세요.

for (int j = 1; j k = k 4;
}

for (int i = 1; i for (int j = 1; j k = k i j;
}
}

첫 번째 루프는 10번 실행되고, 두 번째 루프는 20 * n번 실행됩니다. 따라서 루프의 시간 복잡도는 다음과 같습니다.

T(n) = 10*c 20*c*n = O(n)

실시예 6

다음 선택 문을 고려하세요.

if (list.contains(e)) {
System.out.println(e);
}
또 다른
for (객체 t: 목록) {
System.out.println(t);
}

목록에 n개의 요소가 포함되어 있다고 가정합니다. list.contains(e)의 실행 시간은 O(n)입니다. else 절의 루프에는 O(n) 시간이 걸립니다. 따라서 전체 명령문의 시간 복잡도는

실시예 7

정수 n에 대한 a^n 계산을 고려해보세요. 간단한 알고리즘은 다음과 같이 n배를 곱합니다.

결과 = 1;
for (int i = 1; i 결과 *= a;

알고리즘은 O(n) 시간이 걸립니다. 일반성을 잃지 않고 n = 2^k라고 가정합니다. 다음 구성표를 사용하여 알고리즘을 개선할 수 있습니다.

결과 = a;
for (int i = 1; i 결과 = 결과 * 결과;

알고리즘은 O(logn) 시간이 걸립니다. 임의의 n에 대해 알고리즘을 수정하여 복잡성이 여전히 O(logn)임을 증명할 수 있습니다.

간단하게 하기 위해 0(logn) = 0(log2n) = 0(logan)이므로 상수 밑수는 생략합니다.