어떤 알고리즘 실행 시간 모델이 있습니까?알고리즘의 실행 시간을 모델링하는 방법은 무엇입니까?
우리 모두는 mergesort가 bublesort보다 빠르다고 예상하며, mergesort는 bubblesort에 대해 O (n log n)와 O (n)를 비교합니다. 다른 알고리즘 용
경우 등
포인터 디 레퍼런스 어레이 조회, 고정 된 크기의 정수 산술과 같은 다른 작업 (이상이 비교 교환), 카운트 다른 무엇 실행 시간을 모델링하는 방법이 ?
내가 아는 한 가지는 디스크에서 읽고 읽은 블록 수를 계산하는 것입니다. 오랜 설명을 보려면 When does Big-O notation fail?에 대한 제 응답을 참조하십시오.
또 하나는 캐시 누락 횟수를 계산합니다. 이것은 메모리 계층의 모든 레벨을 살펴봄으로써 I/O 모델을 확장합니다.
분산 알고리즘 (보안 다중 계산과 같은)의 경우 세 번째는 네트워크를 통해 전송되는 데이터의 양을 계산하는 것입니다 (일반적으로 통신 라운드 또는 메시지 수에서 측정 됨).
알고리즘의 성능을 예측하기 위해 계산에 포함되는 또 다른 흥미로운 사항은 무엇입니까?
또한 이 모델이 얼마나 좋습니까? 필자가 들었을 때, 캐시 잊어 버림 알고리즘은 디스크의 데이터에 대해 I/O 효율적인 알고리즘과 경쟁 할 수 있지만 메모리 내 알고리즘에는 경쟁력이 없습니다.
특히 : 특정 인스턴스에서 이러한 모델이 상대적 성능을 잘못 예측합니까? 내 자신의 실험에 따르면 피보나치 힙은 데이터가 메모리에 들어가기에 충분할 정도로 작 으면 Dijstra의 최단 경로 (바이너리 힙 대비)가 빨라지지 않는다.
"다른 흥미로운 점은 무엇입니까?"실제 질문이 아닙니까? 아마 제목을 조정할거야? –
재미있는 스레드지만 요점은 아닙니다. – ralphtheninja
O (n2)에 정사각형을 올바르게 포맷하려면 +1, P –