무작위 알고리즘의 분류 따라 기회가

무작위 알고리즘에 대한 Wikipedia 에서

예상되는 실행 시간이나 메모리 사용량을 줄이기 위해 임의의 입력을 사용하는 알고리즘 을 구분 해야하지만 항상 제한된 시간 내에 올바른 결과로 종료해야하며
확률 적 알고리즘 은 임의의 입력에 따라 기회가 있습니다 실패를 알리거나 종료하지 않음으로써 잘못된 결과 (Monte Carlo 알고리즘)를 생성하거나 결과 (Las Vegas 알고리즘)를 생성하지 못하는

  1. “첫 번째 종류의 알고리즘 이 임의의 입력을 사용하여 예상 실행 시간이나 메모리 사용량을 줄이는 방법이 궁금 하지만 항상 제한된 시간 내에 올바른 결과로 종료됩니까?
  2. 결과를 얻지 못할 수있는 Las Vegas 알고리즘과 차이점은 무엇입니까?
  3. 내가 올바르게 이해하면 확률 알고리즘과 무작위 알고리즘은 같은 개념이 아닙니다. 확률 알고리즘은 랜덤 알고리즘의 한 종류 일 뿐이며, 다른 알고리즘은 랜덤 입력을 사용하여 예상 실행 시간이나 메모리 사용량을 줄이지 만 항상 제한된 시간 내에 올바른 결과로 종료됩니까?

답변

  1. 영형(엔2)

    영형(엔로그⁡엔)

    영형(엔2)

    영형(엔로그⁡엔)

  2. 이것은 Las Vegas 알고리즘의 하위 집합을 제공합니다. 라스 베이거스 알고리즘은 (낮은 확률로) 전혀 더 이상 종료되지 않을 가능성을 허용합니다.

  3. 이것들은 실제로 몬테카를로 알고리즘의 한 유형일뿐입니다. 대답은 틀릴 수 있습니다 (낮은 확률로). 적어도 개념적으로는 대답하지 않을 수도 있습니다.

물론 남은 세부 사항이 많이 있습니다. 복잡한 아이디어 ZPP, RP 및 BPP를 찾아보고 이러한 아이디어를 공식화 할 수 있습니다.

답변

무작위 알고리즘 과 확률 알고리즘 이라는 두 용어 는 서로 다른 두 가지 상황에서 사용됩니다. 무작위 알고리즘 은 결정 론적 알고리즘 과 달리 무작위성을 사용 하는 알고리즘 입니다. 확률 알고리즘 , 예를 들어 우선 성 테스트를위한 확률 알고리즘은 임의성을 사용하고 약간의 희망이 있으면 오류를 일으킬 수있는 알고리즘입니다.

Monte Carlo 알고리즘 과 Las Vegas 알고리즘 간에 중요한 차이점이 있습니다 . Las Vegas 알고리즘은 항상 정답을 반환하는 무작위 알고리즘이지만 실행 시간은 동전 던지기에 따라 다릅니다. 예를 들어 정수 인수 분해 알고리즘 – 항상 올바른 인수를 반환하지만 실행 시간은 임의성에 따라 다릅니다. Las Vegas 알고리즘의 실행 시간 (인수 분해 알고리즘)을 명시 할 때 실제로 예상 실행 시간을 명시합니다 . 운이 좋지 않으면 알고리즘이 더 오래 실행될 수 있습니다.

반면에 Monte Carlo 알고리즘은 실행 시간이 미리 설정된 무작위 알고리즘입니다. 이러한 알고리즘은 실수를 할 수 있지만 일반적으로 오류 확률은 매우 낮습니다. 좋은 예는 확률 론적 원시성 테스트입니다. 이 알고리즘은 매우 빠르지 만 오류가 발생할 수 있습니다. 그러나 오류 확률은 느리므로 실제로는 실수하지 않습니다.

모든 Las Vegas 알고리즘은 오랜 시간이 지난 후에 실행을 중지하여 Monte Carlo 알고리즘으로 변환 할 수 있으므로 Las Vegas 알고리즘은 Monte Carlo 알고리즘보다 “더 나은”의미를 갖습니다.

답변