버블정렬 시간복잡도에대한 새로운 관점.

전공공부를 하다 꽤 흥미로운 부분을 발견했네요.

통상적으론 버블정렬의 최선, 평균, 최악의 시간복잡도가 O(n^2)으로 알고있습니다.

하지만 주어진 배열이 이미 정렬되어있는 상태이고 교환횟수를 따로 저장해두는 변수를 선언한다면?

이때 최선의 경우엔 시간복잡도가 O(n)이 되지않을까라는 부분을 알게됐네요.

시중에 다양한 서적들을 읽으며 공부하고 있지만 이런 방식으로 접근가능한건 처음알았네요 ㅎㅎ..

출처는 A book on C입니다!