평균 시간복잡도

[자료구조/C++] 순차 탐색 알고리즘 평균 시간 복잡도 (Linear Search Algorithm Average Time Complexity)

바로 이전에 순차 탐색 알고리즘에 대해서 깊게 탐구해보았다. 그러나 평균 시간 복잡도를 좀 더 제대로 확인할 수 있는 방법을 생각해보았다. 내가 구한 공식과 실제 값을 비교해볼 수 있는 프로그램을 구현하는 것이다. 그래서 해당 코드를 직접 수정하여, 예측값과 10000번의 테스트를 통해 얻은 실제 평균값을 비교하는 것이다. 배열 내에 값이 존재할 확률(p)는 50%로 설정해두었다. 구현 #include #include #include #include #include using namespace std; int LinearSearch(vector x, int target) { for (int i = 0; i < x.size(); i++) if (x[i] == target) return i; return -..