코딩 인터뷰 완전 분석 - big O

주제

• 알고리즘의 효율성을 나타내는 지표에 대해 알아보자.

노트

• big O에 대해 학습하고 예제를 풀던 중 좋은 예제라고 생각되어 정리하려고 한다.

• 여러 개의 문자열로 구성된 배열이 주어졌을 때 각각의 문자열을 먼저 정렬하고 그다음에 전체 문자열을 사전 순으로 다시 정렬하는 알고리즘이 있다고 가정하자. 이 알고리즘의 수행 시간은 어떻게 되겠는가?

• 이 big O에 대한 개념이나 쉬운 예제들을 이해하는데 큰 어려움은 없었다. 하지만 이 문제는 일종의 버릇처럼 대답하던 나의 답변을 고쳐준 좋은 예제였다.

 

• 시간 복잡도를 표현할 때 N을 사용하기보다는 의도가 드러나도록 변수명을 설정하라.

• 가장 길이가 긴 문자열의 길이를 s라 하자.

• 배열의 길이를 a라 하자.

 

• 이제 알고리즘의 시간 복잡도에 대해 알아보자.

• 하나의 문자열을 정렬하는데 드는 시간은 O(s*logs)이다.

• quick sort의 평균적인 시간을 고려해보면 문자열 s가 분할되는 깊이는 logs이고 각 단계에서 s번의 비교가 진행된다. 따라서 하나의 문자열을 정렬하는데 드는 시간은 O(s*logs)이다.

• 이러한 문자열이 a개 있으므로 각각의 문자열을 먼저 정렬하는 시간은 O(aslogs)이다.

  

• 전체 문자열을 사전 순으로 다시 정렬 하는데 드는 시간은 얼마나 걸릴까?

• quick sort의 시간 복잡도가 O(nlogn)이므로 O(aloga)가 걸린다.

 

• 라고 생각하면 문자열이라는 특성을 고려하지 않은 답변이다.

• 위에서 말한 정렬하는데 드는 시간은 각 원소를 비교하는 시간이 계산되지 않았다.

• 서로 다른 두 문자열을 비교하는데 O(s)의 시간이 소요되므로 전체 문자열을 사전 순으로 다시 정렬하는데 드는 시간은 O(saloga)이다.

• 따라서 각각의 문자열을 먼저 정렬하는데 드는 시간 O(a_s_logs)과 전체 문자열을 사전순으로 다시 정렬하는데 드는 시간 O(s_a_loga)을 더하면 O(a*s(loga+logs))가 된다.