0
간단한 질문 :평균 사례 복잡성 - 선형 알고리즘 계산
선형 검색 알고리즘 (특정 조건까지 모든 요소를 한 번 통과 할 것입니다)이있는 경우 평균 사례 복잡성을 어떻게 계산할 수 있습니까? n = 500이라면? 최악의 경우와 가장 좋은 경우는 쉽습니다.
A
답변
3
평균적인 경우도 마찬가지로 간단합니다. 찾는 항목이 고유 한 경우 평균적으로 목록 + 0.5 중간을보아야합니다.
목록의 모든 항목을 한 번 조회한다고 가정 해 봅시다. 첫 번째 항목을 조회 할 때 1 개의 항목을 검사해야합니다. 두 번째 항목을 조회 할 때 2 개의 항목을 검사해야합니다. 총 검사 건수는
1 + 2 + 3 + ... + 500 = 125250
입니다. 따라서 조회수가 125250 건이됩니다. 평균적으로 조회 당 250.5 검사입니다.
조회 패턴이 비 균일하면 평균 사례가 비뚤어집니다 (예를 들어 목록 시작 부분에서 항목을 더 자주 조회하거나 반복되는 항목 중 어느 것이 든 충분하다고 판단하는 경우)
+0
그래, 그건 내가 생각했던 것과 비슷하지만, 선생님이 강의 중에 옳지 않다고 말하는 이유를 기억합니다. 그러나 그것은 나에게 완벽하게 이해됩니다. 감사! – user1062704
+0
실제로 복잡도를 계산할 때 놀랐던 점은 250 대신 250.5라고 대답했습니다. – tfinniga
+1
기본 산수 시리즈 (1 + 2 + ... + n)의 합계에 대한 수식을 기억하면 놀라실 수 있습니다. . 그것은 (용어의 수) * (1 학기 + 마지막 학기)/2입니다. 이 합계를 용어 수로 나누기 때문에 계산하는 것은 단지 첫 번째 용어 + 마지막 용어/2입니다.이 경우 (500 + 1)/2 – Shashank
0
선형 검색 알고리즘의 평균 복잡도는 n + 2 입니다. 여기서 n은 목록의 요소 수입니다.
관련 문제
- 1. 시간 복잡성 - 알고리즘의 최악 사례 계산
- 2. 선형 검색 알고리즘의 평균 사례 실행 시간
- 3. stl 벡터로 계산 복잡성?
- 4. 복잡성 (큰 O 계산)
- 5. 최악의 경우의 알고리즘 복잡성 결정
- 6. 선형 정렬 알고리즘
- 7. 계산 평균
- 8. 비교 정렬 알고리즘 복잡성
- 9. 알고리즘 분석 (복잡성)
- 10. 복잡성 네트워크의 구심 알고리즘
- 11. 함수의 복잡성 및 알고리즘
- 12. 프림과 Kruskal의 알고리즘 복잡성
- 13. quicksort의 알고리즘 복잡성?
- 14. 확률로 평균 케이스 복잡성 찾기
- 15. 알고리즘의 효율성과 복잡성 계산
- 16. 시간 계산 복잡성?
- 17. 한정된 공간 평균 계산
- 18. 계산 평균
- 19. 계산 평균
- 20. 행렬로부터 요소 평균 평균 계산
- 21. 다른 프로그래밍 패러다임의 알고리즘 복잡성
- 22. SQL 사례 및 평균 선택
- 23. f (n) 비용을 사용한 연산의 알고리즘 복잡성
- 24. 선형 회귀 실제 사례
- 25. MATLAB의 k- 평균 알고리즘
- 26. 파이썬 k- 평균 알고리즘
- 27. 이동 평균 알고리즘 문제
- 28. 선형 패턴 일치를위한 알고리즘?
- 29. C에서 선형 증가 알고리즘
- 30. 윤곽을 채우기위한 선형 알고리즘
선형 적으로 계산하는 경우 250이되지 않습니까? – joshstrike