구현하기에는 너무 복잡한 합법적 인 유틸리티 알고리즘은 무엇입니까?
명확하게하자 : 나는 현재 asymptotic 최적 행렬 곱셈 알고리즘 (Coppersmith-Winograd)과 같은 알고리즘을 찾고 있지 않지만 구현하기에는 합리적이지만 실제로는 쓸모없는 상수를 가지고 있습니다. 실용적인 가치를 가질 수는 있지만 구현이 불가능하거나 매우 인공적인 환경에서만 구현되거나 현저히 특수한 용도로만 구현 될 수있는 코딩이 어려운 알고리즘을 찾고 있습니다.
또한 무증상은 좋지만 실제 성능은 좋지 않은 구현이 거의 불가능한 알고리즘도 환영합니다.
답변
Chazelle은 간단한 다각형 을 삼각 측량하기 위한 선형 시간 알고리즘을 제공했습니다 . Skiena는 “존재 증명으로 더 자격이 있다는 것을 구현하기에는 충분치 않다”고 썼다 (p.575, Algorithm Design Manual).
답변
릿슈 알고리즘 초등학교 부정적분을 계산. Wikipedia에 따르면 소프트웨어 패키지는 복잡성으로 인해 전체 알고리즘을 구현하는 것으로 알려져 있지 않습니다.
답변
Robertson-Seymour 결과를 사용하여 고정 된 마이너를 제외하는 그래프와 관련된 항목에 대해 “폴리 타임”알고리즘을 유추하는 알고리즘은 문제를 요구합니다. 결과에 숨겨진 상수는 “은하계”입니다.
답변
Dan Willard의 “최악의 최악의 시간에 순차적으로 정렬 된 파일에서 삽입 및 삭제를 수행하기위한 밀도 제어 알고리즘” 은 삽입 및 삭제와 함께 크기가 인 배열로 정렬 된 세트를 유지하는 알고리즘을 설명합니다. 최악의 시간입니다. 여기서 는 페이지 크기입니다.
O(n)O(log2nB)
B
이 논문의 길이는 55 페이지이며 결론은 저자가 공간상의 이유로 설명하지 않은 상수에 대한 몇 가지 개선점을 지적합니다. 이것은 아마도 상수가 그렇게 은하 적이 지 않다고 생각하며,이 데이터 구조는 “합법적 인 유틸리티”일 것입니다. 특히 여러 번 인용 되었기 때문입니다.
답변
Qian의 선형 시간 고차 패턴 통합 알고리즘은 복잡한 AFAIK로 인해 구현 된 적이 없습니다.
답변
그래프를 고정 된 표면에 삽입 할 수 있는지 확인하는 선형 시간 알고리즘
Ken-ichi Kawarabayashi, Bojan Mohar, Bruce A. Reed : 임의의 표면에 그래프를 포함하고 경계가있는 나무 너비 그래프의 속을위한 더 간단한 선형 시간 알고리즘. FOCS 2008 : 771-780.
Bojan Mohar : 임의의 표면에 그래프를 포함하기위한 선형 시간 알고리즘. SIAM J. 이산 수학. 12 (1) : 6-26 (1999)
답변
나는 (내가 RNA 이차 구조 예측뿐만 아니라, 단백질 접힘과의 비교에 대해 생각하고 있지만)가 실제로 할 수있는 방법을 유용 모르겠지만, 볼프강 하켄 첫 번째 준 다항식 시간의 매듭이 인 여부를 결정하는 알고리즘을 단순 루프 ( Theorie der Normalflächen. Acta Math. 105, 1961, 245–375 쪽). 제가 기억 하듯이, 수십 년 후에 구현하기에는 여전히 너무 복잡합니다.
Wikipedia가 믿어지면 나중에 몇 가지 다른 알고리즘이 주어졌으며 “이 알고리즘의 복잡성을 이해하는 것이 활발한 연구 분야입니다.”