[알고리즘] 시간복잡도 예제 15종


시간 복잡도에 대해서 들어보셨지요?

시간 복잡도를 처음 공부하시면, 예제와 함께 하는 것이 정말 많은 도움이 됩니다. 저도 역시 그랬고요.. 사실, 예제 찾기가 쉽지가 않아요. 그리고, 시간복잡도를 구하는 문제가 면접에서 면접에서 나온다면, 잘 기억하세요.

'정말 집중하셔야 해요'

내가 만든 코드가 아닌데 거기서 시간 복잡도를 구하려면 먼저 자세히 살펴봐야 합니다. 코드리뷰를 먼저 하셔야 하죠. 무턱대고 구하시면 틀릴 가능성이 커요. 왜냐하면, 함정을 숨겨 놓을 것이라서요. 분명!

시간 복잡도 때문에 집중하지 못해서 면접에서 떨어졌다면? 걱정마세요.. 그렇다고 당신이 실력이 없는 것이 아닙니다. 이 시간복잡도는 중요하지만, 아주 아주 작은 빙산의 일각일 뿐이에요. 내가 작성한 코드의 시간복잡도만 정확히 구하실 줄 알면 됩니다. 장기적으로 그런 의미에서 이 예제들이 많이 도움이 되었으면 좋겠습니다.

아직 시간복잡도가 무엇인지 모르신다면, 다른 포스트 글을 참고해 주세요.

그리고 시간 복잡도는 C나 Java로 많이 출제 됩니다. 그래서 파이썬 코드보다 아래 코드로 보시면 더욱 문제 풀이에 수월하실 거에요.

>>딩그르르의 시간복잡도에 관한 포스트 읽기



문제 #1. 

int a = 0, b = 0;

for (i = 1; i < N; i++) {
a = a + rand();
}

for (j = 2; j < M; j++) {
b = b + rand();
}





문제 #2. 

a = 0, b = 0;    
for (i = 0; i < N; i++) {
for (j = 0; j < N; j++) {
a = a + j;
}
}
for (k = 0; k < N; k++) {
b = b + k;
}





문제 #3.

int a = 0;
for (i = 0; i < N; i++) {
for (j = N; j > i; j--) {
a = a + i + j;
}
}





문제 #4. 우리는 두가지 알고리즘을 가지고 있습니다, 'Algo A'와 'Algo B' 이지요. 여기서, 'Algo A'가 'Algo B' 보다 점근적으로 더 효과적이라는 말은 무슨 뜻인지 아래 선택 답지에서 골라보세요.

  1.  Algo A가 어떤 크기의 입력이 들어와도 항상 빠르다.
  2. Algo A가 입력 크기가 클 경우 빠르다.
  3. Algo A가 입력 크기가 작을 경우 빠르다.
  4. Algo B가 항상 더 빠르다.
  5. Algo A가 입력 크기에 따라 메모리 관리능력이 효과적이다.





문제 #5.

int a = 0, i = N;
while (i > 0) {
a += i;
i /= 2;
}





문제 #6.

int count = 0;
for (int i = N; i > 0; i /= 2) {
for (int j = 0; j < i; j++) {
count += 1;
}
}
  1.  O(N * N)
  2.  O(N * log N)
  3.  O(N * log(log(N)))
  4.  O(N)
  5.  O(N * Sqrt(N))







문제 #7.

int i, j, k = 0;
for (i = n/2; i <= n; i++) {
for (j = 2; j <= n; j = j * 2) {
k = k + n/2;
}
}
  1.  Θ(n)
  2.  Θ(nLogn)
  3.  Θ(n^2)
  4.  Θ(n^2 / Logn)
  5.  Θ(n^2Logn)


** Big-Θ 문제는 잘 안나옵니다. 

만약 어떤 알고리즘의 시간복잡도가 Big-O로 표기했을 때 O(n) 이고 Big- Ω로 표기해도 O(n) 이라고 가정해 봅시다.

이런 경우에 이 알고리즘은 Θ(n)이 될 수 있습니다. 만약 Big-O로 표기했을 때 O(n) 인데 Big- Ω로는 다른 값이 나온다면, 이 알고리즘은 Θ값으로 표기할 수 없습니다. 그래서 Big-Θ 문제를 푸시려면, 시간 복잡도를 표기하는 Big-O, Big- Ω, Big-Θ 를 모두 알아야 하기 때문에 아주 가아아아끔 가뭄에 콩 나듯 출제됩니다. 그래서 정답 옵션 중, '빅-세타로 표현할 수 없음.' 이 있으면 골치 아픕니다. 근데... 면접관님들도 잘 모르실듯...;;; 한 느낌적인 느낌? Big-O 시간복잡도를 제외한, Big-O 공간복잡도, Big- Ω, Big-Θ 는 평소에 잘 쓰이지 않습니다. 우리는 모두 인간이라 잘 안쓰면.. 까먹.. ㅜㅜ





문제 #8.

int gcd(int n, int m) {
if (n%m ==0) return m;
if (n < m) swap(n, m);
while (m > 0) {
n = n%m;
swap(n, m);
}
return n;
} # 조건 : n 은 m 보다 항상 큽니다.





문제 #9. 다음 보기중 O(n^2)가 아닌 것은 무엇인가요?

  1.  (15^10) * n + 12099
  2.  n^1.98
  3.  n^3 / (sqrt(n))
  4.  (2^20) * n







문제 #10. 아래 보기 중 가장 빠른 반복문을 고르세요.(n은 양의 정수)

  1. for(i = 0; i < n; i++)
  2. for(i = 0; i < n; i += 2)
  3. for(i = 1; i < n; i *= 2)
  4. for(i = n; i > -1; i /= 2)





문제 #11. 가장 빠른 순서대로 나열하세요.

f1(n) = 2^n
f2(n) = n^(3/2)
f3(n) = n Log n
f4(n) = n^(Log n) f5(n) = n!
  1. f3(), f2(), f4(), f1(), f5()
  2. f3(), f2(), f1(), f4(), f5()
  3. f2(), f3(), f1(), f4(), f5()
  4. f2(), f3(), f4(), f1(), f5()





문제 #12. 

/* 
* V는 이미 정렬되어 있습니다.
* V.size() = N
* searchNumOccurrence(V, k, 0, N-1) 가 호출되었습니다.
*/
int myFunction(vector<int> &V, int k, int start, int end) {
if (start > end) return 0;
int mid = (start + end) / 2;
if (V[mid] < k) return myFunction(V, k, mid + 1, end);
if (V[mid] > k) return myFunction(V, k, start, mid - 1);
return myFunction(V, k, start, mid - 1) + 1 + myFunction(V, k, mid + 1, end);
}
  1.  O(sqrt N)
  2.  O(log N)
  3.  O(log^2 N )
  4.  O(N)
  5.  O(N * log N)
  6.  O(N * sqrt N)





문제 #13.

int memo[101][101];
int findMinPath(vector<vector<int> >& V, int r, int c) {
int R = V.size();
int C = V[0].size();
if (r >= R || c >= C) return 100000000; // Infinity
if (r == R - 1 && c == C - 1) return 0;
if (memo[r][c] != -1) return memo[r][c];
memo[r][c] = V[r][c] + min(findMinPath(V, r + 1, c), findMinPath(V, r, c + 1));
return memo[r][c];
}
  1. O(R*C*log(R*C))
  2. O(2^(R + C))
  3. O(R*C)
  4. O(R + C)
  5. O(R*R + C*C)

 




문제 #14.

int j = 0;
for(int i = 0; i < n; ++i) {
while(j < n && arr[i] < arr[j]) {
j++;
}
}
  1.  O(n)
  2.  O(n^2)
  3.  O(nlogn)
  4.  O(n(logn)^2)







문제 #15. 이론적으로 QuickSort의 최악의 시간 복잡도는 어떻게 됩니까?

  1.  O(n)
  2.  O(log n)
  3.  O(n^2)
  4.  O(n log n)
  5.  O(n(log n)^2)



  • [[a.original_name]] ([[a.file_size | fileSizer]])
'시간복잡도 Big O 시리즈' 시리즈 포스트
[알고리즘]시간복잡도 Big O
2020-03-14
[알고리즘] 시간복잡도 예제 15종
2020-03-20
좋아요[[ postLike | likePlus ]]
공유
라이언

“Lead Python Engineer”

댓글 [[totalCommentCount]]
[[ comment.author__nick_name ]] [[ comment.datetime_updated | formatDate]] (수정됨)

[블라인드 처리된 글 입니다.]

답장
[[ sub.author__nick_name ]] [[ sub.datetime_created | formatDate ]] (수정됨)

취소
댓글을 남겨주세요.
'컴퓨터공학' 관련 최신 포스트
[[ post.title ]]
[[ post.datetime_published_from | DateOnly ]]