오늘 알고리즘 수업을 듣다가 Time Complexity 계산방법에 대한 강의 중에 누군가 수업시간에 한 질문,
"우리가 흔히 nlogn 정렬이라고 말하는 퀵 소트의 경우 Worst Case 는 O(n^2) 이 된다. 교수님이 설명하시길 알고리즘의 시작복잡도는 Worst Case 를 기준으로 측정한다고 얘기했는데 퀵소트는 Average Case 를 기준으로 할 때만 O(nlogn) 이 되는 것인데, 그렇다면 과연 퀵 소트를 O(nlogn) 정렬이라고 정렬이라고 부르는 것이 맞는가?"

참고로, 머지 소트(Merge Sort) 와 힙 소트(Heap Sort) 의 경우 Worst Case 에서도 O(nlogn) 에 수행된다.

당시 알고리즘의 Time Complexity 는 Worst Case 를 기준으로 측정한다고 설명하던 강사도 이 질문에 살짝 당황해서 좀 버벅이다가 실제 상황에서는 Average Case 를 대상으로 적용하는 경우가 많기 때문에 퀵 소트를 nlogn 정렬이라고 본다고 설명했다.

평소에 당연히 퀵 소트는 O(nlogn) 이라고만 생각하던 차, 이 질문을 듣고 나도 의문이 생겨서 집에 와서 CLRS 책을 다시 뒤져보았다.

"Quicksort is a sorting algorithm whose worst-case running time is O(N^2) on an input array of n numbers, In spite of this slow worst-case running time, quicksort is often the best practical choice for sorting because it is remarkably efficient on the average: it's expected running time is O(nlogn), and the constant factors hidden in the O(nlon) notation are quite small. It also has the advantage of sorting in place and it works well even in memory environments.

그러니까, Quicksort 는 O(nlong) 에 숨어있는 상수 계수의 크기도 작고, 내부 정렬이며, 평균적으로 가장 빠르게 수행되는 정렬이며, 가상메모리 상에서도 잘 동작하는 일반적으로 가장 좋은 정렬이다는 이야기. partition 의 깊이 logn 과 각 partition 에서의 비교횟수 n 번이 수행되어 Average Case 는 O(nlogn), n-1 과 0 으로 partition 되는 경우 Worst case O(N^2) 이 된다.

결론적으로 Worst-case 가 알고리즘의 시간복잡도를 평가하는 절대적인 기준은 아니란거네..

Average Case 는 대개 계산하기도 힘들고, 현실에서는 입력되는 값의 정확한 분포를 알기 어려우므로 쓰기 힘들다. 
Worst Case 는 알고리즘의 성능을 보여주는 척도가 될 뿐만 아니라 경험적으로 알고리즘의 수행시간은 Worst Case 인 경우의 수행시간과 큰 차이가 나지 않기때문에  일반적으로 알고리즘의 시간복잡도를 말할때는 Worst-Case 기준으로 평가한다.
"어떤 알고리즘의 시간복잡도가 O(n^2) 이라면 이 알고리즘은 최악의 경우 n^2 만큼 수행한다." 는 의미가 된다.

결론적으로 강사가 이런 부분을 명확하게 설명을 안해준거네 -0-
신고
댓글을 달아주세요!
  1. BlogIcon rubyeye 2008.09.16 09:29 신고  댓글주소  수정/삭제  댓글쓰기

    지나가다가 글 하나 올립니다 ㅋ
    quick sort도 worst case O(nlogn)알고리즘이 맞습니다.
    문제가 되는 것이 quick sort에서 각 단계마다 최적의 key값(중앙값)을 O(n)안에 찾을 수 있느냐인데
    k번째 큰 값을 찾는 알고리즘이 O(n)이므로 가능합니다. 따라서 quicksort도 worst case O(nlogn)이 됩니다.
    문제는 이런 식으로 key값을 찾으면 앞에 붙는 상수값이 커져서 practical하게는 더 느려진다는 점이죠...
    즉, quicksort는 이론적으로 worst-case O(nlogn)입니다만, 실제로 사용할 때는 빠른 속도를 위해서
    worst-case O(n^2)이 되더라도 대충(-_-; ) 키값을 찾게 된다는 거죠... 참고하시기 바랍니다 ^^

  2. 고글 2008.09.25 23:45 신고  댓글주소  수정/삭제  댓글쓰기

    형 저도 지나가다가.. 글 씁니다.

    요점을 다 빗나게가 쓴 것 같아서..
    Quick sort의 worst case는 O(N^2) 입니다. 오름차순 혹은 내림차순으로 정렬 되어 있을때 그렇게 되겠죠.
    데이타를 많이 돌려보았을때 최악의 경우에서 Mergesort와 Heapsort 다 O(n log n)을 보장하지만
    실제로 데이타를 돌려보면 Quick sort가 가장 빠른 결과값을 나오게 합니다.

    Notation상 분명 Quicksort가 Mergesort나 Heapsort보다 확실히 느려야 하는데 그렇지 않는것은 하드웨어레벨에서 그문제가 발생하는거지요.

    이유는 지역성(Locality) 특성 때문입니다.
    "가상메모리 상에서도 잘 동작하는 일반적으로 가장 좋은 정렬이다는 이야기. "
    이게 locality를 잘 반영했다는 얘긴데.
    지역성에는 locality는 두가지가 있습니다.
    시간지역성과 공간지역성이 있는데 여기에서는 공간지역성을 잘 반영했다라고 이해하시면됩니다.
    시간지역성은 한번 나왔던 애가 다시 또 나올 가능성이 높다는것이고,
    공간 지역성은 한번 발생한곳 주위에서 또 발생할 가능성이 높다는것입니다

    Quicksort를 시뮬레이션 해서 잘 관찰해보면 pivot 주변에서 데이타의 위치 이동이 빈번히 발생하게 됩니다.
    메모리에 데이타를 올리고, 캐쉬에 저장해놓고 쓸 때에, 메모리와 캐쉬 hit rate를 생각해보면 Quicksort가 빠릅니다.

    - 컴구조책 메모리파트에서 이렇게 이유를 밝히고 있습니다.

    P.S. 대학원준비한다고 책 처음부터 끝까지 다 봤더니, 몰랐었던 내용도 많이 알게 됐습니다.

    • BlogIcon mynotepad 2008.09.26 14:33 신고  댓글주소  수정/삭제

      오.. 그렇구나.
      지난 학기에 OS 수업들으면서 Locality 와 cache hit ratio, Page fault 에 대해서 열심히 공부한 기억이 나는구낭.. ㅋ

  3. 김대현 2008.10.22 22:01 신고  댓글주소  수정/삭제  댓글쓰기

    저기..질문좀 할께요

    다항시간(다차시간: Polynomial-time) 라고 나오는데요

    정의를 확실하게 잘 모르겠네요...

    식으로 O(n^2)에서요 O는 뭐고 n은 무엇을 뜻하는 건가요??

    정말 어렵네요..ㅡㅡ;;

    답해주시면 정말 감사하겠습니다.

    kdhenjoy@naver.com

    • BlogIcon mynotepad 2008.10.23 02:33 신고  댓글주소  수정/삭제

      O 는 Big-O 표기법입니다.
      http://search.naver.com/search.naver?sm=tab_hty&where=nexearch&query=big-0+%C7%A5%B1%E2%B9%FD
      검색을 해 보시거나 책을 찾아보시면 잘 나와있습니다.
      n 이 의미하는 것은 정렬해야 하는 숫자의 갯수입니다.

  4. 김대현 2008.10.24 12:33 신고  댓글주소  수정/삭제  댓글쓰기

    감사합니다...근데요 또 궁금점이 있는데요~

    O가 문제 걸리는데 최악의 시간이라는데

    그 시간의 결정은 어떻게 하나요?

    O표기법도 다양하던데..어떤때에 어떤걸 써야 할지...잘 모르겠네요...

    NP Problem을 공부하다가 다항시간이 나와서 이리저리 알아보고 있는데

    정말 어렵네요..ㅠㅠ

    여기 BIG-O표기법은 식이 주어져 있을때 푸는게 맞나요??

    아니면 문제가 주어졌을 때 식으로 전환해서 푸시나요?

    학과 과목도 아니고 처음 배우는 거라서요..ㅠㅠ

    쉽게 기초부터 설명 되어있는 책좀 추천좀 해주세요..ㅠㅠ

    감사합니다

    • BlogIcon mynotepad 2008.10.25 10:06 신고  댓글주소  수정/삭제

      시간복잡도 계산하는 점근적 표기법은 여러가지가 있는데 언제 어떤걸 쓸지는 저도 잘 모르겠네요 -0-
      일반적으로 알고리즘 책에서 Big-O 기준으로 많이 설명하고 저 강의에서도 Big-O 기준으로 설명해서 Big-O 를 예로 든 것 뿐입니다.
      NP 문제나 점근적 표기법을 이해하는데는 제가 읽어본 책들 중에서는 "쉽게 배우는 알고리즘" (문병로 저) 가 매우 좋았습니다.

  5. BlogIcon JM 2008.11.22 15:13 신고  댓글주소  수정/삭제  댓글쓰기

    제가 요즘 시간 복잡도 관련 챕터를 쓰면서 깨닫게 되었는데요, Worst Case 와 Big-O notation 이 밀접하게 연관되어 있어서 사람들이 착각하기 쉬울 뿐, 알고리즘의 시간 복잡도를 평가할 때 항상 최악의 경우를 기준으로 삼는 것은 아닙니다.

    일단 잘 아시다시피 Big-O notation 은 어떤 함수가 주어질 때 그 함수의 상한을 표기하는 방법이죠. (상수 범위 내에서..) 그래서, 크기가 n 인 입력을 해결하기 위한 알고리즘의 수행 시간을 f(n) 라 할 때, f(n) = O(n^2) 이라고 쓰면 실제로 최악의 경우 알고리즘의 시간 복잡도를 나타내게 됩니다. 때문에, 사람들이 알고리즘의 수행 시간을 최악의 경우로 평가한다고 생각하기 쉽죠.

    하지만, 실제로 Big-O notation 은 시간 복잡도의 표기를 간단하게 하기 위해 도입한 방법일 뿐, 알고리즘의 최악의 경우에 대한 시간을 측정하기 위해 도입한 방법은 아니죠. 따라서, Big-O 가 항상 '최악의 경우' 와 연관되어 있다는 직관은 잘못된 것이라고 생각해요.

    퀵소트의 경우, 실제 실행 시간 f(n) 을 보는 것이 아니라 수행 시간의 기대값 (expected running time) g(n) 을 대신 보게 되지요. 이 때 f(n) 의 최고차항과 g(n) 의 최고차항이 각각 n^2 이고 nlgn 이기 때문에 최악의 경우엔 O(n^2), 기대값은 O(nlgn) 이라는 말은 완전히 정당한 것이라는... ^^

    저도 한 때 "Big O 표기법은 최악의 경우를 표기하는 거라는데 왜 퀵소트가 nlgn 이지 -_-" 헷갈려 하던 때가 있었어서.. 사족을 덧붙여 봅니다.

    덧) 구글에 worst case time complexity 를 쳐보니 이 블로그가 2번에 뜨더라고요. 그래서 와서 리플 달아 봤습니다. ^^;

    덧2) 그리고 실제로 대부분 많은 알고리즘의 경우에는 expected running time 과 worst running time 의 order 가 같습니다. 머지소트나 힙소트의 경우에는 n 이 주어졌을 때 실행 시간 함수 f(n) 이 deterministic 하게 결정되기 때문이고.. 선형검색 같은 경우에도, 중간에 찾았을 경우 곧장 리턴하는 방법을 쓰더라도, expected time 은 n/2 이고 worst time 은 n 이니까, O(n) = O(n/2) 죠? ㅎㅎ

    지하철에서 원고하다 장문의 리플을 달아 봤습니다 -_-;

  6. 짱강 2008.12.27 01:11 신고  댓글주소  수정/삭제  댓글쓰기

    전산에서 최악의 경우인 빅O는 굉장히 중요한 의미를 시사한다.
    빅O는 특정 행위를 수행하는데 특정 시간안에 수행됨을 보장함을 의미한다.
    즉, 평균적인 타임이 N에 비례하는 것과 NlogN에 비례하는 두개의 알고리즘이 있다고 하자.
    이로써는 해당 행위가 언제 끝날 수 있는지 보장되는 것은 아니다.
    반면 최악의 경우 N^2과 NlogN에 비례한다고 하면
    이는 해당 행위가 언제 끝날 수 있는지가 보장이 된다.
    즉, 퀵 소트는 평균적으로 NlogN에 비례하는 다른 소트(힙, 병합, 기수)보다 상대적으로 빠를 수 있지만
    최악의 경우(어느 정도 정렬되어 있는 자료 혹은 어느 정도 역순 정렬되어 있는 자료)의 경우 N^2에 비례하는 속도를 낸다.
    즉, 자료가 어떤 성향이냐에 따라 수행 속도의 차이가 크다는 것이다.
    결론적으로 퀵소트는 최악의 경우 NlogN에 비례하는 (힙, 병합,기수)정렬보다 빠르다고 얘기할 수 없다.

  7. jinagaden 2014.03.21 10:05 신고  댓글주소  수정/삭제  댓글쓰기

    quick sort 공부하면서 얼핏 생각했던 부분이었는데, 검색을 통해서 여기 들어와서
    원글이랑 댓글 보고 많은 생각의 정리를 할 수 있었습니다:) 다들 감사해요!

이름 암호 홈페이지