반응형 램덤 알고리즘1 Randomized Algorithm [ 무작위 알고리즘 ] 무작위 알고리즘(Randomized Algorithm) or 랜덤화된 알고리즘은 무작위성을 사용하여 알고리즘의 일부를 랜덤하게 작동하게 만든다. 이런 방식의 알고리즘을 사용하기 좋은 경우는 바로 입력값의 적절한 분포를 알기 어려울 때이다. 입력값의 분포를 모르기 때문에 무작위성을 사용하여 기댓값을 동일한 확률로 처리하기 위함이다. 확률을 따라 운이 좋으면 소요시간이 짧아질 수도 있고 최악의 경우 최대 O(n)까지 비용이 발생한다. O(n)의 뜻을 이해하지 못하겠다면, 이전 글인 시간복잡도 관련한 글을 읽어보는 것을 추천한다. (1) 정렬 방법 : Permute-by-sorting 원소마다 임의의 Priority를 할당하고 그 순서대로 정렬한다. import random def pe.. 2021. 4. 11. 이전 1 다음 반응형
