[Data Structure / Java] ✒️ 시간 복잡도

---

시간 복잡도

입력되는 데이터의 증가에 따른 성능의 변화를 예측

 

1. O(1)

int function(int[] n) {

    if(n.length < 3)
    return 0;
        
    int a = n[0];
    a += n[1];
    a += n[2];
    
    return a;
}

int배열 n개가 들어오는데 몇개가 들어와도 메소드 안의 처리는 연산의 양은 변하지 않는다.

즉, 변화가 없이 항상 일정하다.

 

2. O(n)

int sum(int[] n) {
    int s = 0;
    
    for (int index : n) {
    	s += index;
    }
    
    return s;
}

int 배열 n개가 들어올 때 메소드 안의 처리하는 연산이 n번 수행된다. 

입력되는 배열 n개에 따라 연산하는 양이 비례한다.

 

3. O(n^2)

void bubbleSort(int[] n) {

    for (int index = 0; index < n.length; index++) {
    	
	 for (int index2 = 0; index2 < n.length; index2++) {
        	
            if (n[index] < n[index2]) {
                int temp = n[index2];
                n[index2] = n[index];
                n[index] = temp;
            }
            
        }
        
    }
    
}

입력되는 배열 n의 개수 만큼 첫번째 for문과 두번째 for문이 돈다. 

예를 들어 배열의 개수가 3이라면 첫번째 for문이 3번 돌고 한번 돌때마다 두번째 for문이 3번씩 돌기 때문에 3^2이다.

 

4. O(longn)

int sum(int[] n) {
    int sum = 0;
    int max = n.length;
    while (max > 0) {
    	sum += n[max - 1];
        max /= 2;
    }
    return sum;
}

입력받는 배열의 개수에 따라 loop를 도는데 돌면 돌수록 절반씩 줄어들고 있다.

즉, 입력 받은 개수가 동작할 때마다 처리되는 범위가 절반씩 줄어들고 있다.

 

Ex) 예외?

int sum(int[] n) {
    int s = 0;
    
    for (int i: n) {
    	s += i;
        
        for (int j = 0; j < 10; j++) {
        	s += j;
        }
    }
    
    return s;
}

 

=  O(n)

why?
int배열이 들어오는데 for문 두개가 돌고 있다.

첫번째 for문은 n개 만큼 돌고, 두번째 for문은 10번 돈다.

시간복잡도는 입력되는 데이터의 개수가 증가할 때 수행해야 하는 처리문이 함께 얼만큼 증가하냐 라는 비율로 본다.

만약 int배열이 10개 들어온다면 첫번째 for문은 10번 돌고 두번째 for문도 10번씩 돈다. 
int배열에 100개가 들어온다면? 첫번째 for문은 100번 돌고 두번째 for문은 여전히 10번씩 돈다.

즉, 입력되는 int 배열 n에 영향을 받는 값은 첫번째 for문 만이다. 그렇기 때문에 O(n)이다.

 

Reference

• 프로그래머스 - [Java] 어서와! 자료구조 알고리즘은 처음이지?

[Java] 어서와! 자료구조 알고리즘은 처음이지?