오늘은 data structure의 마지막! Time Complexity 문제풀이를 하고자한다.
문제 파일이 늦게 도착하는 바람에 문제 풀이가 늦어졌다.
그럼 문제 풀이를 해보도록 하겠다.
- 스택을 연결리스트로 구현했을 때 값 하나를 추가하는 연산의 시간복잡도로 올바른 것은?
A. O(1)
B. O(n)
C. O(log n)
D. O(n log n)풀이)
A. O(1)
-> O, 입력 데이터의 크기와 상관없이 값을 추가하면 언제나 일정한 시간이 걸린다.
B. O(n)
-> X, A번 풀이설명대로 진행되기 때문에 B번부터 D번은 따로 설명을 하진 않겠다.
C. O(log n)
-> X
D. O(n log n)
-> X
따라서 답은 A이다.
- Linked List의 시간 복잡도를 Big-O 표기법으로 나타낸 것 중 틀린 것은?
A. Search - O(n)
B. Insert - O(n)
C. Access - O(1)
D. Deletion - O(n)풀이)
일반적으로 접근, 조회, 삽입, 삭제 시에는 위치가 특정되어지지 않았을 경우 O(n)이 맞다.
따라서 답은 C이다.
- HashTable 삽입 연산의 시간 복잡도를 Big-O 표기법으로 올바르게 나타낸 것은?
(평균적인 기준에 따름)
A. O(1)
B. O(n log n)
C. O(log n)
D. O(n^2)풀이)
A. O(1)
-> O, 입력 데이터의 크기와 상관없이 값을 추가하면 언제나 일정한 시간이 걸린다.
B. O(n log n)
-> X, 역시 A번 설명대로이기 때문에 B번부터 D번까지는 추가 설명을 하진 않겠다.
C. O(log n)
-> X
D. O(n2)
-> X
따라서 답은 A이다.
- 두 알고리즘 A, B의 시간 복잡도가 각각 O(n), O(log n) 라면, 알고리즘 B가 알고리즘 A 보다 항상 빠르다.
풀이)
O(log n)은 후반부로 갈수록 시간이 증가하기 때문에 항상 빠르다고 할 순 없다.
따라서 답은 거짓이다.
- 다음의 시간 복잡도를 가지는 알고리즘들이 있을 때, 가장 느린 것과 가장 빠른 것을 모두 고르면? (단, n ≥ 10,000)
A. O(n log n)
B. O(2^n)
C. O(log n)
D. O(n^2)
E. O(n!)풀이)
일반적으로 효율성 좋은 순서는 다음과 같다.
O(1) < O(log n) < O(n) < O(N log n) < O(n^2) < O(n^3) < O(2^n) < O(n!)
보기에서 가장 느린 것을 꼽자면 O(n!), 가장 빠른 것을 꼽자면 O(log n)이 된다.
따라서 답은 C,E가 된다.
- 다음과 같은 코드의 시간 복잡도로 올바른 것은?
for (let i=0; i<n; i++) {
for (let j=0; j<n; j++) {
// do something
}
}A. O(n)
B. O(n log n)
C. O(n^2)
D. O(n^3)
E. O(log n)풀이)
연산횟수로 계산하자면 n*(n-1)/2 인데, 빅오 표기법으로 따지면 n^2이다.
따라서 답은 C이다.
- 알고리즘의 시간 복잡도를 나타낼 수 있는 표기법이 아닌 것은?
A. Big-Ω
B. Big-O
C. Big-Θ
D. Big-α풀이)
알고리즘의 시간 복잡도를 나타낼 수 있는 표기법의 종류는 다음과 같다.
1 . Big-O (빅 오 표기법) : O( ) => 기껏해야
(최악의 경우)
점근적 상한선 : (아무리 나빠도 시간이 이보다 덜 걸림, 최악의 시나리오)
주로, 이 표기법을 사용한다.
2 . Big-Omega (빅 오메가 표기법) : Ω( )=> 적어도
(최선의 경우)
점근적 하한선 : (최소 이만한 시간이 걸림, 최선의 시나리오)
3 . Big-Theta (빅 세타 표기법) : Θ( ) => 대략
(평균의 경우)
빅 오,빅 오메가 표기법의 절충된 방법이다. (즉,교집합)
따라서 답은 D이다.
- 다음과 같은 코드의 시간 복잡도로 올바른 것은?
for (let i=0; i<n; i++) {
for (let j=0; j<i; j++) {
// do something
}
}A. O(n)
B. O(n*(n-1)/ 2)
C. O(n*(n+1)/ 2)
D. O(n^2)
E. O(log n)풀이)
6번 문제와 같은 풀이다.
따라서 답은 D이다.
- 다음과 같은 코드의 시간 복잡도를 올바르게 나타낸 것은?
let i = N;
while (parseInt(i > 0)) {
i = i / 2;
}A. O(n)
B. O(log n)
C. O(n log n)
D. O(n^2)풀이)
let i = N;
while (parseInt(i > 0)) {
i = i / 2;
}
이 문제를 풀때 N을 10이라고 간주해보겠다.
10
5
2.5인데 parseInt 니까 2
1.25인데 parseInt 니까 1
0.625인데 parseInt 니까 0
따라서 답은 B이다.
- 다음과 같은 코드의 시간 복잡도를 올바르게 나타낸 것은?
for (let i = 0; i < n; i++) {
i *= k;
}A. O(n)
B. O(n*k)
C. O(logn k)
D. O(logk n)
E. O(log n)풀이)
for (let i = 0; i < n; i++) {
i *= k;
}
이 문제를 해석하면 다음과 같다.
k를 몇번 곱해야 n보다 커질까? k/n
logk(n)= ?
O(logkn), O(log n)도 맞다.
따라서 답은 D,E이다.
