[알고리즘] 간단하게 이해한 시간복잡도(feat. Java)

프로그램을 실행하는데 최대 시간을 계산해야 한다.

이 때 사용되는 것이 O이다.

 

예를 들어 자바에서 다음의 코드를 실행하는데 걸리는 시간을 계산해 보면,

* 한 줄당 1로 계산한다.

 

public class Main {
	public static void main(String[] args) {
		System.out.println("Hello World!");
	}	
}

 

System.out.println("Hello World!"); 한 줄만 계산되므로 1이다.

 

public class Main {
	public static void main(String[] args) {
		for(int i = 0; i<n; i++){
        	system.out.println(i);
        }
	}	
}

 

int i = 0 한 번, i<n이 n번, i++이 n번 그리고 출력 함수가 n번 실행되므로 총 3n+1이다.

 

여기서 최고차항인 n을 빅오 표기법으로 나타내어 O(n)으로 표기한 게 시간복잡도이다.

 

프로그램을 실행했을 때,

 

n이 2차항이라면 1차항일 때보다(교차점 이후로) 프로그램 실행 시간이 훨씬 길어진다.

 

 

 

그러므로 O(n^2)보다 O(n)이 실행시간이 더 짧다는 것이다.