알고리즘 개요
시간 복잡도: 입력의 크기와 문제를 해결하는데 걸리는 시간의 상관관계
빅오표기법: 주어진 식을 값이 가장 큰 대표항만 남겨서 나타내는 방법
O(1) : 1,5, 10 값이 상수,
데이터가 커져도 실행시간은 그대로이다
for(i=1; i<=n; i*2) {
...
}O(N): 5N+3, 2N+, 10N
데이터의 양에 따라 실행시간이 일차함수적으로 늘어난다.
ex) 주어진 배열에서 개수를 찾는 문제
int func1(int n) {
int a=0;
for (k=1;k≤N;k+1){
if(n%3 ==0 ||n%5 ==0) {
a=a+n;
}
}
}
⇒ O(N)
O(lgN):로그시간 연산횟수가 logN에 비례해서 증가하면 O(lgN)이 된다. (ex) 이진탐색
func6(k, arr, left, right){
if(left>rigth) return -1;
m=(left+right)/2;
if(arr[m]==k) return m;
else if(arr[m]>k) return func6(k,arr,left,m-1);
else return func(k,arr,m+1,right);
}O(NlgN):
NlgN 이진탐색처럼 나누어서 필요한 부분만 취하는 것이아니라 나눈뒤에 모두 선택하는 정렬이다. 그러므로 나누는과정 O(lgN) 모두 선택 O(N) = O(NlgN) ex)합병정렬
O(N^2): N제곱, 실행시간이 2차함수적으로 늘어난다. 시간,상대적으로 느린 탐색에 해당된다. 정렬문제에서 시간초과가 뜬다면 N^2대신 logN이나 NlgN 으로 해결해야한다. ex)이중 for문, 완전탐색
int func2(int[] a ,int N) {
for (k=0; k≤N;k=k+1) {
for(
}
}
⇒ O(N2)
O(2^n): Fibonacci 수열처럼 함수가 호출 될때마다 재귀함수를 두번더 호출해야되는 로직일때, 데이터가 늘어날때마다 n^2보다도 현저하게 실행시간이 늘어남.
func(n,arr) {
if(n<=0) return 0;
else if(n==1) return arr[n]=1;
return arr[n]=func(n-1,r)+func(n-2,r);
O(루트N): 제곱수 반환시 시간 복잡도
int func4(int N) {
int a;
for(int i=1; i*i<N;i=i+1){
a=i*i;
}
return a;
}