목록알고리즘 (1)

포시코딩

이중 for문의 시간복잡도

예제를 통해 이중 for문의 시간복잡도를 구해보자 algorithm sum(A, n): sum = 0# 1번 for i=0 to n-1 do# n번 for j=i to n-1 do# 아래에서 설명 sum += A[i] * A[j]# 3번 return sum 각 for문의 돌아간 횟수 i j 0 n 1 n-1 2 n-2 ... ... n-1 n-(n-1)=1 식으로 나타내기 for j=i to n-1 do # 여기서 i가 n-1이라면 j=도 n-1이 되고 to n-1 즉, n-1이 n-1이 될 때 까지니까 한 번 돌게 된다. # 규칙을 부여해서 찾는다면 n-(i의 시작 수)가 되니 n-(n-1)이 되어 n-n+1 즉, 1이 되는 방법도 있다. 결국 이중 for문의 횟수는 위 표의 j 밑에 있는 값들을 모두..
자료구조알고리즘/이론 2022. 12. 12. 00:11
이전 Prev 1 Next 다음