asymptotic runtime, big-O

시간복잡도

- 문제를 해결하는데 걸리는 시간과 입력의 함수관계

- 데이터가 증가함에 따른 처리시간의 증가율을 측정하기 위해 만들어졌으므로 상수는 무시된다.

 

O(1)

입력 데이터에 상관없이 일정한 시간이 걸린다.

O(n)

데이터가 늘어날수록 데이터가 비례하여 시간이 늘어남

 

n^2 + n 의 시간복잡도는 O(n^2)

n^4 + n^2 의 시간복잡도는 O(n^4)

for (int i = 0; i < n; i++) {
}

for (int i = 0; i < m; i++) {
}

시간 복잡도는 O(n+m)

 

for (int i = 0; i < n; i++) {
     for (int j = 0; j < m; j++) {
                
    }
}

시간 복잡도 O(n^2)

 

while (i > n) {
   
}

시간 복잡도 O(log n)

 

for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
		for (int a = 0; a < k; k++) {

    	}
    }
}

시간 복잡도 O(n^3)

 

for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
		for (int a = 0; a < k; k++) {
        	for (int b = 0; b < 100; b++) {

    		}
    	}
    }
}

시간 복잡도 O(n^3)

O(n^4)가 아닌 O(n^3)이 된다

 

for (int i = 0; i < n; i =i*3) {

}

시간 복잡도 O(log N)