하고 싶은거 할래

하고 싶은거 할래

  • 분류 전체보기
    • CS(Computer Science)
      • Algorithm
      • DataBase
      • Reading Paper
    • 개발
      • CleanCode
      • 기타
      • Spring
  • 홈
  • 태그
  • 방명록
RSS 피드
로그인
로그아웃 글쓰기 관리

하고 싶은거 할래

컨텐츠 검색

태그

클린코드 알고리즘 데이터 모델링 데이터베이스 인덱스 몽고디비 다이나믹 프로그래밍 quicksort DP 정렬 스프링 MongoDB 인기 게시글 동시성 레디스 스키마 동적 계획법 시간복잡도 동적계획법 데이터베이스 인덱스

최근글

댓글

공지사항

아카이브

퀵소트 시간복잡도(1)

  • QuickSort(2)-알고리즘04

    Worst Case Partitioning 퀵 정렬의 수행시간은 분할 후 양쪽 구역의 크기가 비슷한지 그렇지 않은지에 따라 달라진다. 즉 퀵 정렬에서 pivot을 기준으로 분할을 할 때, pivot이 무엇이냐에 따라 연산횟수가 달라진다. 연산횟수를 최대로 만드는 pivot은 무엇일까? 일단 퀵 정렬의 시간복잡도는 T(n)= T(q) + T(n-q-1) + O(n) 이었다. 여기서 q가 n-1이라면 T(n)= T(n-1) + T(1) + O(n) = T(n-2) + T(1) + O(n-1) + T(1) + O(n) =... 이다. 한마디로 배열을 n-1개짜리와 1개짜리 로 분할을 하는 pivot을 선택하는 것이 퀵정렬에서의 최악의 경우이다. 따라서 T(n)=O(n^2) 인데 이를 증명하자. 재귀트리를 이용..

    2023.06.30
이전
1
다음
티스토리
© 2018 TISTORY. All rights reserved.

티스토리툴바