걸음 수 방법은 알고리즘을 분석하는 방법 중 하나입니다. 이 방법에서는 하나의 명령어가 실행되는 횟수를 계산합니다. 그로부터 알고리즘의 복잡성을 찾으려고 노력할 것입니다.
순차 검색을 수행하는 알고리즘이 하나 있다고 가정합니다. 각 명령어가 c1, c2, … 실행하는 데 시간이 걸리면 이 알고리즘의 시간 복잡도를 알아내려고 합니다.
| 알고리즘 | 횟수 | 비용 |
|---|---|---|
| seqSearch(arr, n, 키) 나는 :=0 내가 부서지다 종료 완료 내가 반환 | 1 n+1 N 0/1 1 | c1 c2 c3 c4 c5 |
이제 실행 횟수를 곱하여 비용을 추가하면(최악의 상황을 고려하여) 다음을 얻습니다.
비용=c1+(n+1)c 2+nc3+c 4+c 5
비용=c1+nc 2+c2+nc 3+c 4+c5
비용=n(c 2+c3)+c 1+c 4+c5
비용=n(c 2+c3)+C
c1 + c4 + c5가 C라고 생각하면 최종 방정식은 직선 y =mx + b와 같습니다. 따라서 우리는 함수가 선형이라고 말할 수 있습니다. 복잡성은 O(n)입니다.