시간 복잡도(Time Complexity) feat. 빅오 표기법

📌시간복잡도(Time Complexity)란?

---

알고리즘이 수행되는 데 걸리는 시간을 입력 크기(input size)에 대한 함수로 표현한 것

 

1초 → 약 1억 번의 연산이 이루어진다. 

 

 

 

 

 

 

 

📌시간 복잡도 유형

---

💡빅 오메가(Ω(n)) = lower bound (하한선)
    • 최선일 때(best case)의 연산 횟수를 나타낸 표기법

💡빅 세터(ϴ(n))
    • 보통일 때(average case)의 연산 횟수를 나타낸 표기법

💡빅 오(O(n)) = upper bound (상한선)
    • 최악일 때(worst case)의 연산 횟수를 나타낸 표기법

 

 

❗코딩테스트를 할 때에는 다양한 테스트 케이스를 수행해 모든 케이스를 통과해야하므로 빅 오 표기법(최악의 경우)을 염두에 둬야 한다.

 

 

 

 

 

 

📌빅오 표기법 시간 복잡도

---

💡 빅오 표기법 읽는 법/ 의미

O(수행하는데 걸리는 시간)  

 

예시)

•  O(1): 한번에 찾을 수 있음
•  O(log n) : log n 번만에 찾을 수 있음 

 

💡 속도 비교

O(1) < O(logN) < O(N) < O(NlogN) < O(N^2) < O(2^N) < O(N!)

 

❗보통 정렬 알고리즘이 NlogN 수준이다. 

 

 

 

📌시간복잡도 계산 방법

---

시간복잡도를 따질 때에는 데이터의 개수를 먼저 본다.

 

💡연산 횟수 계산 방법 : 알고리즘 시간 복잡도 X 데이터의 크기

 

 

 

각 라인을 수행하기 위해 필요한 스텝 수는 상수라고 가정하자.

int[] multiply(int[] inputs, int multiplier) {
	int[] nums = new int[inputs.length]; //c1: 1번 수행
	for(int i = 0; i < inputs.length; i++) { //c2: N+1번 수행(N번 + 루프 탈출을 위한 검사 1번)
		nums[i] = inputs[i]*multiplier; // c3: N번수행 
	}
	return nums; //c4: 1번 수행
}

 

 

 

이 메서드를 수행하기 위한 수행 시간

  T(N) = c1 + c2*(N+1) + c3*N + 1
    = (c2+c3)*N + c1 + c2 + 1
    = a*N + b

 

여기서 N이 작을 땐 실행 시간이 의미가 없고, N →∞일 때 실행 시간이 중요. 이것을 점근적 분석이라고 한다.

 

<점근적 분석>
임의의 함수 N → ∞일 때 어떤 함수 형태에 근접해지는지 분석

 

 

※ a*N + b

• N이 커질수록 덜 중요한 것은 제거. → b 제거
• 최고차항의 계수는 의미가 없다. → a 제거

     따라서 T(N) = ϴ(N)이 된다.

 

 

📌시간 복잡도 예제

---

💡Idea
    • 상수는 시간 복잡도 계산에서 제외
    • 가장 많이 중첩된 반복문의 수행 횟수가 시간복잡도의 기준이 됨 

 

아래의 예제들에서 N번 실행되는 반복문은 실제로 검사를 N+1번 실행하지만 상수는 의미가 없으므로 편의상 N이라고 하자.

예제1)

public class 시간복잡도_판별원리1 {
	public static void main(String[] args) {
		int N = 100000; //1번 수행
		int cnt = 0; //1번 수행 
		for (int i = 0; i< N; i++ { 
			System.out.println("연산 횟수:" + cnt++); //반복문 N번 수행 
		}
	}
}

 

연산횟수 :  O(n)

 

예제2)

public class 시간복잡도_판별원리2 {
	public static void main(String[] args) {
		int N = 100000;
		int cnt = 0;
		for (int i = 0; i< N; i++ { //1번 반복문 N번 실행 
			System.out.println("연산 횟수:" + cnt++);
		}
		for (int i = 0; i< N; i++ { //2번 반복문 N번 실행
			System.out.println("연산 횟수:" + cnt++);
		}
		for (int i = 0; i< N; i++ { //3번 반복문 N번 실행
			System.out.println("연산 횟수:" + cnt++);
		}
	}
}

연산 횟수 = N + N + N = O(3N)
    → 상수는 시간 복잡도 계산에서 제외하므로 O(n)

 

따라서 위의 두 예제는 시간복잡도가 같다.

→ 즉 for문이 몇 개이든, 단일 for문이 여러 개 있는 것은 시간복잡도가 같다는 의미.

 

예제3)

public class 시간복잡도_판별원리3 {
	public static void main(String[] args) {
		int N = 100000;
		int cnt = 0;
		for (int i = 0; i< N; i++ { //N번 실행
				for (int j = 0; i< N; i++ { //N번 실행 
			System.out.println("연산 횟수:" + cnt++);
				}
		}
	}
}		

시간복잡도 : O(n^2)
바깥루프(N번), 안쪽 루프(N번) → N*N = N^2

 

따라서 일반 for문 10개보다 이중 for문 하나가 더 시간복잡도가 크다.

 

 

 

 

 

📌Binary Search에 대한 시간복잡도

---

💡Binary Search : 이미 정렬된 데이터에서 내가 찾으려는 데이터 위치를 반환하는 검색
     → 앞에서부터 순차적으로 찾지 않고, 중간값부터 찾음

 

💡 탐색 방법

1. 이미 데이터가 정렬되어 있어야 함
2. 검색 범위의 중간 요소를 선택하고, 찾으려는 값과 비교
3. 찾으려는 수가 중간 요소보다 크면 오른쪽, 작으면 왼쪽과 다시 비교
4. 2, 3번을 반복하여 중간 요소가 찾으려는 수와 일치하면 탐색을 멈춘다.

 

 

💡 예시

 

 

💡일반식 구하기

 

매번 실행할 때마다 1/2씩 사이즈가 줄어든다. 몇 번만에 사이즈가 1이 되는가?

 

• worst case 일 때

  → input size를 N이라고 했을 때 ϴ(logN)

• best case 일 때(한 번에 찾을 때)

  → ϴ(1)

 

 

 

 

 

 

 

끝까지 읽어주셔서 감사합니다 :)

Have a good day🐱

---

📢

1. 개발자 준비생이 공부한 내용을 정리한 글입니다. 내용에 오류가 있을 수 있습니다.
2. 위와 같은 이유로 내용에 대한 지적과 조언은 감사하게 받습니다.
3. 이 글의 내용은 계속 공부함으로써 언제든지 추가/수정 될 수 있습니다.