알고리즘(1) - 시간복잡도, 공간복잡도

알고리즘을 만들고 해결할 때 성능의 판단은 시간복잡도와 공간복잡도에 맡기게 된다.
예를들어 다음과같은 알고리즘이 있다고 해보자.

---

public class algorithm{
	public static void main(String [] args){
 		int a = 10000;
        for(int i=0; i<a; i++){
        	System.out.println("만번");
    	}
    }
}

---

간단히 문장을 10000번 출력하는 함수가 있다고 했을 때 시간복잡도는 O(a)가 된다.
컴퓨터가 1초에 1억번의 연산을 한다고 했을 때 10000번은 문제가 없지만 a가 10억이 된다면 1초의 시간제한에 문제가 될 수 있다. 이런식으로 성능을 시간복잡도로 측정할 수 있다.
또다른 방식은 공간복잡도인데 공간복잡도는 시간복잡도보다 성능측정의 우선순위가 뒤떨어진다. 공간복잡도는 메모리사용량에 따라 측정되는데, 예전컴퓨터와는 다르게 현재 컴퓨터의 메모리가 꽉찰일은 거의 없기때문에 그렇다.
그렇다해도 공간복잡도를 아예 고려하지 않는것은 바람직하지않고, 10억번의 반복이 있을 때 결과물이 나오면 바로 출력하게끔 함으로써 메모리낭비를 줄일 수 있다.