자바 자료구조#00. 시간복잡도

시간복잡도

• 입력되는 데이터의 증가에 따른 성능의 변화를 예측
• 알고리즘이 n개의 데이터에 대해 얼마나 많은 연산을 수행하는지
• 증가하는 n에 대한 성능의 변화율
• 정확한 측정값이 아님
• 정확한 연산의 횟수가 아니라, n의 갯수에 따라 연산이 증가하는 비율을 의미
• Big O 표기법 O(n)
• 데이터 수 대비 시간의 증가율을 그래프로 그려보면 각 연산의 복잡도가 각각의 그래프와 유사하게 증가함
• 시간복잡도 : O(1) > O(logn) > O(n) > O(n2)
  

---

O(1)

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

배열의 길이가 달라진다 해도 연산의 양은 변하지 않음. 항상 고정.

---

O(n)

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

배열의 길이가 n개 증가하면, 연산의 처리 횟수도 n번 증가

---

O(n2)

void bubbleSort(int[] n) {
	for (int i = 0; i < n.length; i++) {
    	for (int j = 0; i < n.length; j++) {
        	if (n[i] < n[j]) {
            	int temp = n[j];
                n[j] = n[i];
                n[i] = tmep;
            }
        }
    }
}

배열의 길이가 n개 증가하면, 연산의 처리 횟수는 n 제곱 만큼 증가

---

O(logn)

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

배열의 길이가 n개일때, 연산을 수행하는 횟수는 절반씩 감소

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