Big O notation
복잡도에 가장 영향을 많이 끼치는 항의 상수인자를 빼고 나머지항을 없애서복잡도를나타내는표기법!상수시간 시간 복잡도 O(1) : 입력 크기와 상관없이 일정한 시간 복잡도를 가지는 것 (e.g. : 입력과 출력, 곱하기, 간단한 비교if문, 배열의 인덱스)#includeusing namespace std;int N, cnt;void Func(int N) { cnt++; cout > N; Func(N); return 0;}이 함수의 시간복잡도를 점화식으로~ N=1일때 cnt = 4(1+3^1)N=2일때 cnt = 13 (+9 =1+ 3^2)N=3일때 cnt = 40(+27= 3^3)N=4일때 cnt = 121(+81 = 3^4)...즉 등비수열의 합이다~그러므로.. 가장 주요한 영향을 주는 3^n을 빼고 나..
자료구조&알고리즘/C++
2024. 12. 13. 00:44
