4강 알고리즘 시간복잡도 2

자료구조 알고리즘의 시간복잡도는 원래 모든 입력에 대해 기본연산의 횟수를 더하여 평균을 구해야 한다.
하지만 입력의 개수가 무한대라서 현실적으로 불가능하기때문에 가장 안좋은 입력에 대한 기본연산 횟수를 측정한다
그러면 어떤 입력의 수행시간도 그거보다는 작다.

arrayMax 함수를 보면 currentMax = A[0] 에서 = 에 의해 기본연산 횟수 1 이 추가되고,
for문은 n-1번 루프, if문에서는 < 연산자와 = 연산자로 인해 2번의 연산횟수가 추가되므로 2n-2가 된다.
그래서 이 함수의 연산횟수는 2n-1이다.

알고리즘 수행시간은 최악의 입력에 대한 기본연산 횟수 이므로, 이 함수의 시간복잡도, 수행시간은 2n-1이 된다.

sum1과 sum2의 수행시간을 보면 각각 n, n^2에 비례하는걸 알 수 있다.
n^2가 n보다 걸리는 시간이 더 빨리 늘어나므로 수행시간이 더 오래걸린다.