[부스트코스]알고리즘 퀴즈 4

Q>

버블 정렬이 효율적인 경우는 어떤 경우인가요?

반대로 어떤 경우에 비효율적이게 될까요?

 

A>

버블 정렬의 장/단점 중 장점으로 데이터는 제자리에 정렬되므로 메모리 오버헤드가 거의 없으며,
일단 정렬되면 데이터는 메모리에 저장되어 처리 준비가 된다. 
가장 큰 단점은 분류에 걸리는 시간이다. 
평균 시간은 테이블 요소의 수가 증가함에 따라 거의 기하급수적으로 증가한다. 
버블 정렬의 시간 공간 복잡성을 보면
최악의 경우 시간 복잡성 [Big-O ]: O(n2)
모범 사례 시간 복잡성 [Big-Ω]: O(n)
평균 시간 복잡성 [Big-θ]: O(n2)
공간 복잡성: O(1)

 

https://www.boostcourse.org/cs112

모두를 위한 컴퓨터 과학 (CS50 2019)