잉?
이게 무슨 말이냐 하시면
자 우선 저는 여려분이 bogo sort를 알고 있다는 가정 하에서 말할꺼에요.
만약 모르시는 분을 위해 이게 알고리즘이에요
1. 만약 리스트가 정렬되어 있으면 스탑
2. 만약 정렬 안됐으면 무작위로 섞습니다.
3. 스탭 1으로
보기에는 말도 안되는 정렬 알고리즘입니다. 아주 비 효율적으로 보이죠.
하지만!
양자 컴퓨팅에서라면?! 말이 다릅니다.
양자 물리학에선 아주아주 다양한 우주가 존재하거든요!
리스트를 무작위로 섞는 과정에서 아~~주 아주 많은 무한대의 우주가
만들어 집니다! 어떤 우주에선 무작위로 짠! 한번 섞었는데
정렬이 되어있고, 다른 우주에선 짠! 했는데 정렬이 안되어 있을 수도 있겠죠?
자! 이 경우 양자 컴퓨팅에선 bogo sort를 O(n)으로 만들 수 있습니다!!
새로운 알고리즘이에요
1. 무작위로 리스트를 섞습니다.
2. 만약 정렬이 됐다면 스탑!
3. 만약 정렬이 안됐으면 그 우주 전체를 파괴합니다.
살아남은 사람들만 그 리스트가 한번에 정렬이 됐는지 아닌지 알겠군요.
이건 아주아주아주 효율적인 알고리즘입니다.
리스트가 정렬됐는지 아닌지 체크 하는건 겨우
n-1 번의 비교만 필요합니다. 그리고 가정상 우주 전체 파괴하는데 O(1) 만큼 시간이 걸린다면.
bogo sort의 Big O 는 O(n) 이라는 아주아주 효율적인 알고리즘이 됩니다.
와우 :D
[출처]http://www.mathnews.uwaterloo.ca/Issues/mn11103/QuantumBogoSort.php
글쓰기