선택한 단어 수는 입니다.
최소 단어 이상 선택하여야 합니다.
최소 단어 이상 선택하여야 합니다.
선택한 단어 수는 30입니다.
최대 10 단어까지만 선택 가능합니다.
최대 10 단어까지만 선택 가능합니다.
문제 정의
- 또한 벤치마킹을 통해 runtime과 관련해 QuickRotation이 기존 모든 알고리즘 보다 더 적은 (가장 적은) 시간을 필요로 함을 보이고자 한다. Juggling 알고리즘은 비록 필요로 하는 assignments 횟수와 관련해 이론적으로 가장 효율적인 알고리즘에 해당하나 실제에 있어서 요구하는 runtime과 관련해 4개의 알고리즘 중 가장 비 효율적인 알고리즘에 해당하는 이례적 사실을 실험결과로 소개한다.
- 증명. recursion height에 관해 귀납적으로 증명해 보이고자 한다.
- 또한 벤치마킹을 통해 runtime과 관련해 QuickRotation이 기존 모든 알고리즘 보다 더 적은 (가장 적은) 시간을 필요로 함을 보이고자 한다.
- 길이 m의 세 수열이 4m에 해당하는 assignments횟수를 소비 하며 순환방식으로 수열의 위치 (position)를 바꿔가는 floating hole기술의 활용을 통해 QuickRotation이 기존의 모든 알고리즘과는 차별화 되는 우수성을 지닐 수 있게 되었다. 이 논문에서 우리는 복잡도 분석을 통해 QuickRotation이 BlockRotation과 Reversal 알고리즘보다 더 적은 assignments 횟수를 요구함을 증명해 보이고자 한다. 또한 벤치마킹을 통해 runtime과 관련해 QuickRotation이 기존 모든 알고리즘 보다 더 적은 (가장 적은) 시간을 필요로 함을 보이고자 한다.
- Juggling 알고리즘이 가장 적은 횟수의 assignments를 요구하는 사실이 [2]에서 소개 되었다. 이러한 이론적으로 옵티멀한 특성에도 불구하고 Juggling 알고리즘이 실제에 있어서 가장 오랜 runtime을 필요로 하는 알고리즘에 해당함을 다음 단원에 소개 하고자 한다. 이로부터 더 적은 횟수의 assignments 요구가 항상 더 적은 runtime을 요구하지는 않는다는 사실에 대한 하나의 반례로 Juggling 알고리즘을 들 수 있음을 알 수 있다.
- Reversal 알고리즘이 요구하는 assignments 횟수를 함수 ξ (m,n)로 묘사하고자 하며 [4]에서 이 함수식이 모든 m >0,n >0에 대해 ξ(m,n) =3([(m+n) / 2] + [n/2] +[m/2])이 됨이 소개 되었다. 이제 QuickRotation이 Reversal 알고리즘보다 더 적은 횟수의 assignments를 요구함을 증명하고자 한다.
- 이제 모든 (m,n),m >0,n >0,m≠n 에 대해 Quick-Rotation이 BlockRotation보다 더 적은 횟수의 assignments를 요구함을 증명하고자 한다.
- 최근 우리가 추가로 ”floating hole“기술에 기반한 새로운 블록로테이션 알고리즘을 [3]에서 소개했으며 이 알고리즘을 ”QuickRotation“이라 명명하고자 한다.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.