Cracking the Coding Interview, 6th edition, Introduction, 6. Big O
Cracking the Coding Interview, 189 Programming Questions & Solutions, Grale Laakmann McDowell
이 개념은 중요하기 때문에 전체 (긴) 장을 투여하고 있습니다. Big O 시간은 알고리즘의 효율성을 설명하는 데 사용하는 언어와 측정 항목입니다. 이를 완전히 이해하지 못하면 알고리즘 개발에 심각한 어려움이 생길 수 있습니다. 빅 오를 정말 이해하지 못한 경우, 빅 오에 대한 이해가 없어서 알고리즘이 빨라지거나 느려지는 시점을 판단하기 어려울 뿐만 아니라, 빅 오에 대한 이해를 부족히 알고 있는 것으로 비판을 받을 수도 있습니다. 이 개념을 숙달하세요.
An Analogy
상상해보십시오. 하드 드라이브에 파일이 있고, 그 파일을 국경을 넘어 사는 친구에게 최대한 빨리 보내야하는 상황입니다. 파일을 친구에게 어떻게 보내야 할까요? 대부분의 사람들의 첫 번째 생각은 이메일, FTP 또는 기타 전자적인 수단일 것입니다. 이 생각은 합리적이지만, 반만 정답입니다. 파일이 작은 경우, 5~10시간이 걸릴 것입니다. 공항에 도착하고 비행기를 타고 친구에게 전달하는 데 시간이 걸리기 때문입니다. 그러나 파일이 정말로 큰 경우 어떨까요? 1 테라바이트 (1 TB) 파일은 전자적으로 전송하는 데 하루 이상이 걸릴 수 있습니다. 파일을 그냥 비행기로 전달하는 것이 훨씬 빠릅니다. 파일이 그렇게 긴급하다면 (비용이 문제가 아니라면) 그냥 비행기로 전달하는 것이 좋을 수도 있습니다. 항공편이 없다면 어떻게 할까요? 대륙을 가로지르는 대신 차를 타고 이동해야한다면, 아직도 정말 큰 파일의 경우에는 차를 타고 이동하는 것이 더 빠를 수 있습니다.
Time Complexity
이것이 점진적 실행 시간 또는 빅 오 시간(big O time) 개념입니다. 데이터 전송 “알고리즘” 실행 시간을 다음과 같이 설명할 수 있습니다.
전자적 전송: O(s), 여기서 s는 파일의 크기입니다. 이것은 파일을 전송하는 데 걸리는 시간이 파일의 크기와 선형으로 증가한다는 것을 의미합니다. (네, 이것은 조금 간략화된 설명이지만 이러한 목적에는 적당합니다.)
비행기 전송: 파일 크기에 대한 O(1). 파일의 크기가 증가하더라도 파일을 친구에게 전달하는 데 더 오랜 시간이 걸리지 않습니다. 시간은 일정합니다.
무슨 큰 상수가 있고 선형 증가가 얼마나 느리든지, 선형은 어느 순간 상수를 초과할 것입니다.
이 외에도 많은 실행 시간이 있습니다. 가장 일반적인 몇 가지 예로는 O(log N), O(N log N), O(N), O(N^2), 그리고 O(2^N) 등이 있습니다. 가능한 실행 시간의 고정된 목록은 없습니다. 실행 시간에는 여러 변수가 포함될 수도 있습니다. 예를 들어, w 미터 너비와 h 미터 높이를 가진 울타리를 칠하는 데 걸리는 시간은 O(wh)로 설명할 수 있습니다. 만약 p 번의 도장이 필요하다면 시간은 O(whp)로 설명할 수 있습니다.
Big O, Big Theta, and Big Omega
만약 학교에서 big O에 대한 학습 경험이 없다면, 이 소절은 건너뛰는 것이 좋습니다. 이것은 도움보다 혼란스러울 수 있습니다. 이 “FYI”는 주로 big O를 이미 배운 사람들을 위해 용어의 모호함을 해소하기 위해 여기에 있습니다. 학계에서는 런타임을 설명하기 위해 big O, big Ω, big Θ를 사용합니다.
O (big O): 학계에서는 big O가 시간의 상한선을 설명합니다. 배열의 모든 값을 출력하는 알고리즘은 O(N)으로 설명할 수 있지만 O(N^2), O(2^N) (또는 다른 많은 big O 시간)으로도 설명할 수 있습니다. 이 알고리즘은 이러한 모든 시간보다 빠르거나 같으므로 이들은 시간의 상한선입니다. 이는 작거나 같다는 관계와 유사합니다. 만약 Bob이 X 세라면 (아무도 130세를 넘지 않는다고 가정합니다), X < 130이라고 말할 수 있습니다. X < 1, 0 또는 X < 1, 0 0 8, 6 6 0 이라고 말하는 것도 옳습니다. 기술적으로는 사실이지만 (그리 유용하지 않습니다). 마찬가지로 배열의 값 출력을 위한 간단한 알고리즘은 O(N)뿐만 아니라 O(M^3) 또는 O(N)보다 더 큰 런타임이라고 할 수 있습니다. Ω (big Ω): 학계에서는 Ω가 하한선에 해당하는 동일한 개념입니다. 배열의 값을 출력하는 것은 Ω(N)뿐만 아니라 Ω(log M) 및 Ω(1)입니다. 결국, 그것이 이러한 런타임보다 빠르지 않을 것임을 알 수 있습니다. Θ (big Θ): 학계에서는 Θ는 0 및 Ω 둘 다를 의미합니다. 즉, 알고리즘이 0(N)이면 0(N) 및 Ω(N) 모두인 경우입니다. Θ는 런타임에 대한 엄밀한 한계를 제공합니다. 산업 (그리고 따라서 면접에서)에서는 사람들이 O와 Θ를 병합한 것처럼 보입니다. 산업에서의 big O의 의미는 학계에서의 big O가 의미하는 것과 유사하기 때문에 배열을 출력하는 것을 0(N^2)로 설명하는 것은 부정확한 것으로 간주됩니다. 산업에서는 항상 런타임의 가장 엄밀한 설명을 제공하려고 합니다. 이 책에서는 산업이 일반적으로 사용하는 방식대로 big O를 사용할 것입니다.
Best Case, Worst Case, and Expected Case
알고리즘의 런타임을 설명하는 방법을 실제로 세 가지 다른 방식으로 설명할 수 있습니다.
이것을 퀵소트의 관점에서 살펴보겠습니다. 퀵소트는 “피벗”으로 임의의 요소를 선택하고 피벗보다 작은 요소가 피벗보다 큰 요소보다 앞에 나타나도록 배열 내의 값을 교환합니다. 이렇게 하면 “부분 정렬”이 생성됩니다. 그런 다음 비슷한 프로세스를 사용하여 왼쪽과 오른쪽 측면을 재귀적으로 정렬합니다.
최선의 경우: 모든 요소가 동일한 경우, 퀵소트는 평균적으로 배열을 한 번 훑기만 할 것입니다. 이것은 O(N)입니다. (실제로 퀵소트의 구현에 약간 의존합니다. 그러나 정렬된 배열에서 매우 빠르게 실행되는 구현이 있습니다.) 최악의 경우: 우리가 매우 불운하게 피벗이 배열에서 반복적으로 가장 큰 요소인 경우 어떻게 될까요? (사실, 이런 일이 쉽게 발생할 수 있습니다. 피벗이 하위 배열의 첫 번째 요소로 선택되고 배열이 반대 순서로 정렬된 경우 이런 상황이 발생합니다.) 이 경우, 우리의 재귀는 배열을 반으로 나누지 않고 하나의 요소로만 줄어들 것입니다. 이것은 O(N^2) 런타임으로 수렴합니다. 기대되는 경우: 보통은 피벗이 매우 낮거나 매우 높을 때가 있지만 계속해서 그렇지는 않을 것입니다. 퀵소트의 런타임은 일반적으로 O(N log N)으로 예상됩니다. 최선의 경우 시간 복잡도를 거의 다루지 않는 이유는 그것이 그다지 유용한 개념이 아니기 때문입니다. 결국 거의 모든 알고리즘에 대해 특별한 경우를 만들어 0(1) 시간을 얻을 수 있습니다.
대부분의 알고리즘에 대해 최악의 경우와 기대되는 경우는 동일합니다. 그러나 때로는 다를 수 있으며 런타임을 두 가지 경우에 대해 설명해야 할 때가 있습니다.
최선/최악/기대되는 경우와 큰 O/큰 Θ/큰 Ω 간의 관계는 무엇인가요? 이러한 개념을 혼동하기 쉽습니다 (아마도 “높은”, “낮은” 및 “정확히 옳은” 몇 가지 개념 때문일 것입니다), 그러나 개념 간에 특별한 관계는 없습니다. 최선, 최악 및 기대되는 경우는 특정 입력 또는 시나리오에 대한 큰 O (또는 큰 Θ) 시간을 설명합니다. 큰 O, 큰 Ω 및 큰 Θ는 런타임의 상한, 하한 및 근접한 한계를 설명합니다.
Space Complexity
시간만이 알고리즘에서 고려해야 할 유일한 요소는 아닙니다. 메모리 또는 공간이 필요한 양도 중요할 수 있습니다. 공간 복잡도는 시간 복잡도와 유사한 개념입니다. 크기 n의 배열을 만들어야 하는 경우, 이는 O(n) 공간이 필요합니다. 크기가 n x n인 2차원 배열이 필요한 경우, 이는 O(n^2) 공간이 필요합니다. 재귀 호출에서 스택 공간도 고려해야 합니다. 예를 들어, 다음과 같은 코드는 O(n) 시간과 O(n) 공간을 필요로 합니다.
int sum(int n) {
if (n <= 0) {
return 0;
}
return n + sum(n - 1);
}
sum(4)
-> sum(3)
-> sum(2)
-> sum(1)
-> sum(0)
각각의 호출은 호출 스택에 추가되며 실제 메모리를 차지합니다.
그러나 전체 호출 수가 n이라고 해서 O(n) 공간이 필요한 것은 아닙니다. 아래 함수를 고려해 보십시오. 이 함수는 0과 n 사이의 인접한 요소를 더합니다:
int pairSum(int a, int b) {
return a + b;
}
int pairSumSequence(int n) {
int sum = 0;
for (int i = 0; i < n; i++) {
sum += pairSum(i, i + 1);
}
return sum;
}
pairSum 함수에 대략적으로 O(n) 번의 호출이 있을 것입니다. 그러나 이러한 호출들은 호출 스택에 동시에 존재하지 않으므로 공간 복잡도는 O(1)만 필요합니다.
Drop the Constants
Sig 0 코드가 특정 입력에 대해 0 ( 1 ) 코드보다 더 빠르게 실행될 수 있다는 가능성이 매우 높습니다. Big 0는 단순히 증가율을 설명합니다. 이러한 이유로 우리는 런타임에서 상수를 제거합니다. 누군가가 2개의 (중첩되지 않은) for 루프가 있는 코드를 0 ( 2N )로 설명할 수도 있지만 실제로는 O(N)입니다. 많은 사람들이 이것을 하기를 꺼립니다. 그들은 두 개의 (중첩되지 않은) for 루프가 있는 코드를 계속해서 0 ( 2N )로 보고 더 “정확하게” 보이려고 합니다. 그러나 그렇지 않습니다.
아래 코드를 고려해보세요.
// Min and Max 1
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
for (int x : array) {
if (x < min) min = x;
if (x > max) max = x;
}
// Min and Max 2
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
for (int x : array) {
if (x < min) min = x;
}
for (int x : array) {
if (x > max) max = x;
}
어떤 것이 더 빠를까요? 첫 번째 코드는 하나의 for 루프를 사용하고, 두 번째 코드는 두 개의 for 루프를 사용합니다. 그러나 첫 번째 솔루션은 루프 당 코드 라인이 두 개가 아닌 하나입니다. 만약 명령어의 수를 세려면 어셈블리 수준까지 가서 곱셈이 덧셈보다 더 많은 명령어를 필요로 하는 것과 같은 세부 사항을 고려해야 합니다. 컴파일러가 어떻게 최적화하는지, 하드웨어 및 기타 다양한 세부 사항을 고려해야 합니다. 이것은 굉장히 복잡하며, 이 길을 따라가기 시작하지 마십시오. 빅 오는 실행 시간이 어떻게 확장되는지 표현할 수 있도록 해줍니다. 우리는 단순히 0( N)이 항상 0(N^)보다 낫다는 것을 받아들이면 됩니다.
Drop the Non-Dominant Terms
“0(N^3 + N)”와 같은 표현이 나타날 때 어떻게 해야 할까요? 두 번째 N은 엄격히 상수가 아닙니다. 하지만 그것은 특별히 중요하지 않습니다. 우리는 이미 상수를 무시한다고 말했습니다. 따라서 0(N^3 + N^2)는 0(N^3)이 됩니다. 만약 우리가 후자의 N^2 항에 관심을 가지지 않는다면, 왜 N에 관심을 가져야 할까요? 우리는 그렇지 않습니다.
비지밀한 항들을 제거해야 합니다.
0(N^2 + N)은 O(N^2)이 됩니다. 0(N + log N)은 O(N)이 됩니다. 0(5 * 2^N + 100N^100)은 O(2^N)이 됩니다. 런타임에 합계가 포함될 수 있습니다. 예를 들어, 0(B^2 + A)와 같은 표현은 (A와 B에 대한 특별한 지식 없이는) 축소할 수 없습니다.
런타임에서 여전히 합계가 있을 수 있습니다. 예를 들어, 0(B^2 + A)와 같은 표현은 (A와 B에 대한 특별한 지식 없이는) 축소할 수 없습니다.
다음 그래프는 일반적인 빅 오 시간 중 몇 가지의 증가 속도를 보여줍니다.
/BigO.png)
보시다시피, O(x^2)는 O(x)보다 훨씬 나쁘지만, O(2^x) 또는 O(x!)만큼 나쁘진 않습니다. O(x!)보다 나쁜 런타임도 많이 있으며, O(x^*)나 O(2^x!)와 같은 런타임이 있습니다.
Multi-Part Algorithms: Add vs. Multiply
만약 두 단계를 갖는 알고리즘이 있다면, 그 런타임을 언제 곱하고 언제 더할까요?
이것은 지원자들에게 흔히 혼동을 주는 부분입니다.
// Add the Runtimes: 0(A + B)
for (int a : arrA) {
print(a);
}
for (int b : arrB) {
print(b);
}
// Multiply the Runtimes: 0( A * 8 )
for (int a : arrA) {
for (int b : arrB) {
print(a + "," + b);
}
}
왼쪽 예제에서는 A번의 작업을 수행한 다음 B번의 작업을 수행합니다. 따라서 총 작업량은 O(A + B)입니다. 오른쪽 예제에서는 A의 각 요소마다 B번의 작업을 수행합니다. 따라서 총 작업량은 O(A * B)입니다. 즉,
알고리즘이 “이것을 하고, 모든 작업이 끝나면 그것을 하라” 형태이면 실행 시간을 더합니다. 알고리즘이 “이것을 수행할 때마다 그것을 수행하라” 형태이면 실행 시간을 곱합니다. 이것은 면접에서 쉽게 혼동될 수 있으므로 주의해야 합니다.
Amortized Time
ArrayList (배열 리스트) 또는 동적 크기 조절 배열은 배열의 이점을 가지면서 크기의 유연성을 제공합니다. ArrayList에서는 요소를 삽입할 때 배열의 크기를 초과하는 일이 없으며, 필요할 때 용량(capacity)이 늘어납니다. ArrayList는 배열로 구현되며, 배열이 용량(capacity)을 초과할 때 ArrayList 클래스는 현재 배열의 두 배 크기의 새로운 배열을 만들어서 모든 요소를 새 배열로 복사합니다.
그럼 삽입 작업의 실행 시간을 어떻게 설명할 수 있을까요? 이것은 좀 복잡한 질문입니다. 배열이 가득 차있을 수 있습니다. 배열에 N개의 요소가 있을 때 새 요소를 삽입하면 O(N) 시간이 걸립니다. 새로운 크기가 2N인 배열을 만들고 N개의 요소를 복사해야 하기 때문입니다. 따라서 이 삽입 작업은 O(N) 시간이 소요됩니다. 그러나 이런 상황이 매우 드물게 발생한다는 점도 알고 있습니다. 대부분의 경우에는 삽입이 O(1) 시간에 이루어집니다. 이 두 가지를 동시에 고려해야 합니다. 이것이 바로 “amortized time(분할상환 시간)”이 하는 역할입니다. 이를 통해 최악의 경우가 가끔 발생한다는 것을 설명할 수 있습니다. 그러나 한 번 발생한 후에는 그렇게 오랫동안 다시 발생하지 않으므로 비용이 “분할상환”됩니다.
이 경우 분할상환 시간은 어떻게 되는 걸까요? 요소를 삽입할 때 배열의 크기를 2의 제곱수인 경우에만 용량을 두 배로 늘립니다. 따라서 X개의 요소를 삽입한 후에는 배열 크기가 1, 2, 4, 8, 16, …, X인 경우에만 용량을 두 배로 늘립니다. 이 두 배로 늘리는 작업은 각각 1, 2, 4, 8, 16, 32, 64, …, X번 복사하는 작업입니다. 1 + 2 + 4 + 8 + 16 + … + X의 합은 어떤가요? 이 합은 왼쪽에서 오른쪽으로 읽으면 1에서 시작해서 X까지 두 배로 늘어나고, 오른쪽에서 왼쪽으로 읽으면 X에서 시작해서 절반으로 줄어들며 1에 도달합니다. 그럼 X + 2X + 4X + 8X + … + X의 합은 어떨까요? 대략 2X입니다. 따라서 X개의 삽입 작업은 O(2X) 시간이 소요됩니다. 각 삽입 작업의 분할상환 시간은 O(1)입니다.
Log N Runtimes
우리는 종종 런타임에서 O(log N)을 보게 됩니다. 이것은 어디에서 유래될까요? 예제로 이해해보겠습니다. 이진 검색(binary search)을 살펴보겠습니다. 이진 검색에서는 N개의 원소로 이루어진 정렬된 배열에서 원하는 값을 찾습니다. 먼저 원하는 값 x를 배열의 중간값과 비교합니다. 만약 x가 중간값보다 작다면 배열의 왼쪽 부분에서 검색합니다. x가 중간값과 같다면 찾았다고 반환합니다. x가 중간값보다 크다면 배열의 오른쪽 부분에서 검색합니다.
아래는 배열 {1, 5, 8, 9, 11, 13, 15, 19, 21}에서 9를 찾는 과정입니다.
search 9 within { 1 , 5 , 8 , 9 , 1 1 , 1 3 , 1 5 , 1 9 , 2 1 }
compare 9 to 11 -> s m a l l e r ,
search 9 within { 1 , 5 , 8 , 9 , 1 1 }
compare 9 to 8 -> bigger
search 9 within { 9 , 1 1 }
compare 9 to 9
return
우리는 처음에 N개의 원소로 시작하고, 단 한 번의 단계를 거치면 “N/2”개의 원소로 줄어듭니다. 하나 더의 단계를 거치면 “N/4”개의 원소로 줄어듭니다. 값이나 원소를 찾을 때까지 또는 원소가 한 개가 될 때까지 진행합니다.
전체 런타임은 그런 다음에 얼마나 많은 단계(각 단계마다 N을 2로 나누기)를 걸칠 수 있는지에 달려 있습니다. N이 1이 될 때까지 몇 번 나눌 수 있는지가 중요합니다.
N = 16
N = 8 // devide by 2
N = 4 // devide by 2
N = 2 // devide by 2
N = 1 // devide by 2
이것을 거꾸로 보면 (16에서 1로 가는 대신 1에서 16으로 가는 방식) 1을 2로 얼마나 많이 곱해야 N을 얻을 수 있는지를 생각할 수 있습니다.
N = 1
N = 2 // multiply by 2
N = 4 // multiply by 2
N = 8 // multiply by 2
N = 16 // multiply by 2
이때, 식 2^k = N에서 k는 바로 log가 표현하는 것입니다.
log₂ 16 = 4 log₂ N = k -> 2^k = N
이것은 꼭 기억해둘 가치가 있는 포인트입니다. 원소의 개수가 매 단계마다 반으로 줄어드는 문제를 보면 대부분 O(log N) 런타임일 것입니다.
이것은 균형 잡힌 이진 탐색 트리에서 원소를 찾는 이유와도 같습니다. 각 비교마다 왼쪽 또는 오른쪽으로 이동하게 되므로 절반의 노드가 각 쪽에 있기 때문에 문제 공간을 매 단계마다 절반으로 줄입니다.
그런데 로그의 밑(base)은 어떻게 될까요? 이것은 대부분의 경우에서는 큰 의미가 없습니다. 큰 O 표기법에서는 로그의 밑은 크게 중요하지 않습니다. 더 자세한 설명은 “로그의 밑”을 참조하세요.
Recursive Runtimes
여기 하나 어려운 문제가 있어요. 이 코드의 실행 시간은 어떻게 될까요?
int f(int n) {
if (n <= 1) {
return 1;
}
return f(n - 1) + f{ n - 1};
}
많은 사람들이 뭔가 이유로 f에 대한 두 번의 호출을 보고 0(N^2)로 생각할 것입니다. 이것은 완전히 부정확합니다. 가정을 하기보다는 코드를 통해 실행 시간을 유도해 봅시다. f(4)를 호출한다고 가정해 봅시다. 이는 f(3)을 두 번 호출합니다. 각각의 f(3) 호출은 f(2)를 호출하고, f(2) 호출은 f(1)까지 이어집니다.
/recursive.png)
이 트리에는 얼마나 많은 호출이 있나요? (세지 마세요!) 이 트리는 깊이 N을 가질 것입니다. 각 노드(즉, 함수 호출)는 두 개의 자식을 가지고 있습니다. 따라서 각 수준은 그 위의 수준보다 두 배 더 많은 호출을 가질 것입니다. 각 수준의 노드 수는 다음과 같습니다:
/recursive2.png)
따라서 총 노드 수는 2^0 + 2^1 + 2^2 + … + 2^(N-1) = 2^N - 1개가 됩니다. (자세한 내용은 페이지 630의 “2의 거듭제곱의 합”을 참조하세요.)
이 패턴을 기억하려고 노력하세요. 여러 호출을 수행하는 재귀 함수가 있는 경우 (항상 그렇지는 않지만), 실행 시간은 종종 O(분기^깊이+1)와 같이 보입니다. 여기서 분기는 각 재귀 호출이 갈래치는 횟수입니다. 이 경우에는 O(2^N)이 됩니다.
기억하실 수 있듯이 대문자 O에서 로그의 밑(base)은 상수 배수만 다르기 때문에 상수 배수만큼 다르지 않습니다. 그러나 지수(exponent)에 대해서는 해당되지 않습니다. 지수의 밑은 중요합니다. 2^N과 8^N을 비교해보세요. 8^N을 확장하면 (2^3)^N이 되고, 이는 2^(3N)이 되며, 이는 2^(2^N) * 2^N과 같습니다. 보시다시피, 8^N과 2^N은 2^(2^N)만큼 다릅니다. 이는 상수 배수가 아닙니다!
이 알고리즘의 공간 복잡도는 O(N)입니다. 전체 트리에는 O(2^N)개의 노드가 있지만 어느 시점에나 O(N)만큼의 노드가 존재합니다. 따라서 사용 가능한 메모리는 O(N)만 필요합니다.
Examples and Exercises
Big O 시간 복잡도는 처음에는 어려운 개념일 수 있습니다. 그러나 한 번 이해되면 비교적 쉬워집니다. 동일한 패턴이 반복되며, 나머지는 유도할 수 있습니다. 우리는 쉬운 부분부터 시작해서 점차 어려워질 것입니다.
예제 1 아래 코드의 실행 시간은 얼마인가요?
void foo(int[] array) {
int sum = 0;
int product = 1;
for (int i = 0; i < array.length; i++) {
sum += array[i];
}
for (int i = 0; i < array.length; i++) {
product *= array[i];
}
System.out.println(sum + ", " + product);
}
이 코드는 O(N) 시간이 소요됩니다. 배열을 두 번 반복하는 사실은 중요하지 않습니다.
예제 2 아래 코드의 실행 시간은 얼마인가요?
void printPairs(int[] array) {
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array.length; j++) {
System.out.println(array[i] + "," + array[j]);
}
}
}
내부 for 루프가 O(N)번 반복되고, 이것이 N번 호출됩니다. 따라서 실행 시간은 O(N^2)입니다.
이 코드의 “의미”를 살펴보면 모든 쌍 (두 요소 시퀀스)을 출력하는 것입니다. 총 O(N^2)개의 쌍이 있으므로 실행 시간은 O(N^2)입니다.
예제 3 위 예제와 매우 유사한 코드이지만 이번에는 내부 for 루프가 i + 1에서 시작합니다.
void printUnorderedPairs(int[] array) {
for (int i = 0; i < array.length; i++) {
for (int j = i + 1; j < array.length; j++) {
System.out.println(array[i] + "," + array[j]);
}
}
}
이 코드의 실행 시간은 다음과 같이 유도할 수 있습니다.
이러한 종류의 for 루프 패턴은 매우 일반적입니다. 실행 시간을 알고 있고 깊이 이해하는 것이 중요합니다. 단순히 일반적인 실행 시간을 기억하는 것만으로는 충분하지 않습니다. 깊은 이해가 필요합니다.
Counting the Iterations
처음으로 j가 N - 1번 실행됩니다. 두 번째로는 N - 2번 실행됩니다. 그 다음에는 N - 3번 실행됩니다. 이렇게 반복됩니다. 따라서 총 단계 수는 다음과 같습니다:
(N-l) + (N-2) + (N-3) + … + 2 + 1 » 1 + 2 + 3 + …+ H-l = sum of 1 through N - l
합계 1부터 N-1까지는 N(N-1)/2로 계산할 수 있으며(“Sum of Integers 1 through N” 페이지 참조), 따라서 이 코드의 런타임은 O(N^2)가 됩니다.
WhatltMeans
마찬가지로 코드가 i와 j의 모든 쌍을 반복하면서 j가 i보다 큰 경우에만 작동합니다. 이 쌍은 총 N개 있으며 대략 절반은 i < j를 충족하고, 나머지 절반은 i > j를 충족합니다. 따라서 이 코드는 대략 N^2 / 2 쌍을 반복하므로 런타임은 O(N^2)입니다.
Visualizing What It Does
N = 8일 때, 이 코드는 다음과 같은 (i, j) 쌍을 반복합니다:
이것은 NxN 행렬의 절반과 같아 보이며, 이러한 행렬의 크기는 대략 N^2입니다. 따라서 이 코드의 실행 시간은 대략 O(N^2)입니다.
(0, 1) (0, 2) (0, 3) (0, 4) (0, 5) (0, 6) (0, 7)
(1, 2) (1, 3) (1, 4) (1, 5) (1, 6) (1, 7)
(2, 3) (2, 4) (2, 5) (2, 6) (2, 7)
(3, 4) (3, 5) (3, 6) (3, 7)
(4, 5) (4, 6) (4, 7)
(5, 6) (5, 7)
(6, 7)
이 코드는 대략 NxN 행렬의 절반과 유사한 구조를 가지고 있으며, 이러한 행렬의 크기는 대략 N^2입니다. 따라서 이 코드의 실행 시간은 대략 O(N^2)입니다.
Average Work
외부 루프가 N번 실행되는 것을 알고 있습니다. 내부 루프는 각 반복마다 다양한 작업을 수행하지만 평균 반복을 생각할 수 있습니다. lj의 평균 값은 얼마인가요? 2, 3, 4, 5, 6, 7, 8, 10의 평균 값은 중간 값일 것이므로 대략 5입니다. (물론 더 정확한 답을 제공할 수 있지만, big O에서는 그럴 필요가 없습니다.) 1, 2, 3, …, N의 경우 어떨까요? 이 시퀀스의 평균 값은 N / 2입니다. 따라서 내부 루프가 평균적으로 Y_i의 작업을 수행하고 N번 실행되므로 총 작업량은 Y_i * N입니다. 이는 O(N^2)입니다.
Example 4
이 코드는 이전과 유사하지만 이제 두 가지 다른 배열이 있습니다.
void printUnorderedPairs(int[] arrayA, int[] arrayB) {
for (int i = 0; i < arrayA.length; i++) {
for (int j = 0; j < arrayB.length; j++) {
if (arrayA[i] < arrayB[j]) {
System.out.println(arrayA[i] + ", " + arrayB[j]);
}
}
}
}
우리는 이 분석을 분할할 수 있습니다. j의 for 루프 내 if 문은 상수 시간 순서의 문장들의 연속이기 때문에 O(1) 시간입니다.
우리는 이제 다음과 같이 코드를 가지고 있습니다:
void printUnorderedPairs(int[] arrayA, int[] arrayB) {
for (int i = 0; i < arrayA.length; i++) {
for (int j = 0; j < arrayB.length; j++) {
/* O(1) work */
}
}
}
arrayA의 각 요소에 대해 내부 for 루프는 b번 반복되며, 여기서 b = arrayB.length 입니다. 그러므로 실행 시간은 O(ab)입니다. 만약 당신이 O(N^2)이라고 말했다면, 나중에 이 실수를 기억하세요. 이것은 두 가지 다른 입력이 있기 때문에 O(N^2)이 아닙니다. 두 입력 모두 중요합니다. 이것은 매우 흔한 실수입니다.
예제 5
이 이상한 코드에 대해서는 어떻게 생각하면 될까요?
void printUnorderedPairs(int[] arrayA, int[] arrayB) {
for (int i = 0; i < arrayA.length; i++) {
for (int j = 0; j < arrayB.length; j++) {
for (int k = 0; k < 160800; k++) {
System.out.println(arrayA[i] + "," + arrayB[j]);
}
}
}
}
아무것도 크게 변경된 것이 없습니다. 16만 800개의 작업은 여전히 상수이므로 실행 시간은 여전히 O(ab)입니다.
예제 6
다음 코드는 배열을 뒤집습니다. 이 코드의 실행 시간은 어떻게 될까요?
void reverse(int[] array) {
for (int i = 0; i < array.length / 2; i++) {
int other = array.length - i - 1;
int temp = array[i];
array[i] = array[other];
array[other] = temp;
}
}
이 알고리즘은 O(N) 시간이 걸립니다. 배열의 절반만 반복하기 때문에 (반복 횟수 기준으로) big O 시간에는 영향을 주지 않습니다.
예제 7
다음 중 어떤 것이 O(N)과 동등한가요? 왜 그런가요? • O(N + P), 여기서 P < N • O(2N) • O(N + log N) • O(N + M), 여기서 M < N
이것들을 살펴보겠습니다. • 만약 P < N이라면, N이 우세한 항이므로 O(P)를 삭제할 수 있습니다. • O(2N)은 상수를 삭제하기 때문에 O(N)입니다.
따라서, 위의 두 항은 모두 O(N)과 동등합니다.
• O(N)은 O(log N)을 우세하게 처리하므로 O(log N)을 삭제할 수 있습니다. • N과 M 사이에는 확립된 관계가 없으므로 두 변수를 모두 유지해야 합니다.
따라서, 마지막 항을 제외한 모든 항이 O(N)과 동등합니다.
예제 8
문자열 배열을 입력으로 받아 각 문자열을 정렬한 후 전체 배열을 정렬하는 알고리즘의 실행 시간은 얼마일까요? 많은 지원자들은 다음과 같은 이유로 추론합니다: 각 문자열을 정렬하는 데 O(N log N)이 소요되며, 각 문자열에 대해 이 작업을 수행해야 하므로 O(N * N log N)입니다. 또한 전체 배열을 정렬해야 하므로 추가로 O(M log M) 작업이 필요합니다. 따라서 전체 실행 시간은 O(N^2 log N + N log N)으로, 이는 단순히 O(N log N)입니다. 하지만 이것은 완전히 틀린 추론입니다. 어떤 오류를 발견하셨나요? 문제는 N이 두 가지 다른 방식으로 사용되었다는 점입니다. 한 경우에는 문자열의 길이를 나타내며 (어떤 문자열에 대한 것인지는 명확하지 않음), 다른 경우에는 배열의 길이를 나타냈습니다. 인터뷰에서는 N이라는 변수를 전혀 사용하지 않거나, N이 무엇을 나타낼지 명확히 알 때만 사용하여 이러한 오류를 방지할 수 있습니다. 실제로 여기서는 a와 b 또는 m과 n을 사용하지 않을 것이며, 어떤 것이 어떤 것인지 잊어버리고 섞어버릴 수 있으므로 사용하지 않아야 합니다. O(a:) 실행 시간은 O(a * b) 실행 시간과 완전히 다릅니다. 이를 해결하기 위해 새로운 용어를 정의하고 논리적인 이름을 사용하겠습니다. • S는 가장 긴 문자열의 길이입니다. • a는 배열의 길이입니다. 이제 이를 부분별로 살펴보겠습니다. • 각 문자열을 정렬하는 데 O(s log s)이 소요됩니다. • 이를 모든 문자열에 대해 수행해야 하므로 O(a * s log s)입니다. • 이제 모든 문자열을 정렬해야 합니다. 문자열 비교를 해야 하므로 각 문자열 비교에는 O(s)가 소요됩니다. 전체 문자열 비교 수는 O(a log a)이며, 따라서 이 작업은 O(a * s (log a + log s))입니다. 이것이 최종 실행 시간입니다. 더 줄일 수 있는 방법은 없습니다.
예제 9
이 간단한 코드는 균형 잡힌 이진 탐색 트리의 모든 노드의 값을 합산합니다. 이 코드의 실행 시간은 어떻게 될까요? 단지 이진 탐색 트리라고 해서 그 안에 로그가 있는 것은 아닙니다! 이것을 두 가지 방법으로 살펴볼 수 있습니다.
int sum(Node node) {
if (node == null) {
return 0;
}
return sum(node.left) + node.value + sum(node.right);
}
당신이 말한 것처럼, 이진 탐색 트리가 항상 로그 시간(runtime)이 걸리는 것은 아닙니다. 이 코드의 런타임을 두 가지 관점에서 살펴보겠습니다.
What It Means
가장 직관적인 방법은 이것이 무엇을 의미하는지 생각하는 것입니다. 이 코드는 트리의 각 노드를 한 번씩 방문하며 각 “방문”마다 상수 시간의 작업을 수행합니다(재귀 호출을 제외한 경우). 따라서 런타임은 노드 수에 대해 선형입니다. 노드가 N개인 경우 런타임은 O(N)입니다.
Recursive Pattern
페이지 44에서 여러 가지 분기가 있는 재귀 함수의 런타임에 대한 패턴을 논의했습니다. 이 패턴을 여기서 적용해 보겠습니다.
우리는 여러 개의 분기가 있는 재귀 함수의 런타임이 일반적으로 (^branches’ 3 * 1 1 0 1 )라고 말했습니다. 각 호출마다 두 개의 분기가 있으므로 0 (2 d c * r t h )를 살펴보고 있습니다.
이 시점에서 많은 사람들이 무언가 잘못되었다고 생각할 수 있습니다. 지수 함수를 갖고 있다는 것은 우리의 논리에 문제가 있다거나 지수 시간 알고리즘을 실수로 만들었다는 것을 의미할 것 같습니다. 하지만 두 번째 주장이 맞습니다. 지수 시간 알고리즘이 맞지만 생각보다 나쁘지 않습니다. 어떤 변수에 대해 지수 함수인지 살펴보십시오.
깊이(depth)는 무엇인가요? 트리는 균형 잡힌 이진 탐색 트리입니다. 따라서 총 노드 수가 N이면 깊이(depth)는 대략 l o g N입니다.
| 위의 방정식을 고려하면 0 ( 2 l c | N )을 얻습니다. l o g 2의 의미를 상기해 보십시오: |
2^P = Q ~> l o g 2 Q = P 2 log N은 어떤 것을 의미할까요? 2와 로그 사이에 관계가 있으므로 이를 간단하게 표현할 수 있어야 합니다.
P = 2^l o g 2 N입니다. 로그 2의 정의에 따라 l o g 2 P = l o g 2 (2^l o g 2 N)가 되며, 이것은 P = N을 의미합니다.
P = 2 l o e N l o g 2 P = log 2 (2 l o e N) P = N 2 loe N = N
따라서 이 코드의 런타임은 노드 수인 N에 대해 0 ( N )입니다.
예제 10
다음 메서드는 주어진 숫자가 소수인지 확인합니다. 이 메서드는 주어진 숫자보다 작은 숫자로 나누어 나누어 떨어지는지 확인합니다. 숫자 n이 제곱근보다 큰 숫자로 나누어떨어지는지 확인할 필요가 없기 때문에 제곱근까지만 확인합니다.
예를 들어, 33은 11로 나누어 떨어지지만(11은 33의 제곱근보다 큽니다), 11의 “상대적인” 수는 3입니다(3 * 11 = 33). 33은 이미 3에 의해 소수가 아니라는 것을 알고 있으므로 더 큰 숫자로 나누어봤을 필요가 없습니다.
이 함수의 시간 복잡도는 무엇인가요?
boolean isPrime(int n) {
for (int x = 2; x * x <= n; x++) {
if (n % x == 0) {
return false;
}
}
return true;
}
많은 사람들이 이 질문에 대해 오답을 받습니다. 논리를 신중하게 다룬다면 꽤 쉽습니다. for 루프 내의 작업은 상수입니다. 따라서 우리는 최악의 경우 for 루프가 몇 번 반복되는지만 알면 됩니다. for 루프는 x = 2 일 때 시작해서 x * x = n 일 때 종료됩니다. 다시 말해, x가 n의 제곱근이 되면 멈춥니다. 이 for 루프는 실제로 다음과 같습니다:
boolean isPrime(int n) {
if (n <= 1) {
return false;
}
for (int x = 2; x * x <= n; x++) {
if (n % x == 0) {
return false;
}
}
return true;
}
이 코드는 O(n) 시간에 실행됩니다.
예제 11
다음의 코드는 n factorial을 계산합니다. 시간 복잡도는 무엇입니까?
int factorial (int n) {
if ( n < 0 ) { return -1; }
else if (n == 0) { return 1; }
else { return n * factorial(n-1) };
}
이 코드는 n부터 n - 1로 직선적인 재귀 호출을 수행하여 1까지 이어집니다. 이것은 O(n) 시간이 소요됩니다.