정리에 앞서서 편입을 하여 SW공학을 전공하게 되면서 3학년 때 기본적인 알고리즘과 자료구조에 대해서 공부를 마지막으로 정말 제대로 자료구조와 알고리즘에 대해서 열의를 가지고 공부를 하지 않은 내 자신에게 너무 미안해서...

나 자신에게 남는 공부를 하고 싶다는 생각을 하게 되어 차근차근 정리 해보려고 한다.

천리길도 첫발을 내딛는 것 부터가 시작이다. 도저언!!!

---

시간 복잡도

• 입력된 데이터가 출력할 때까지 걸린 시간
  알고리즘이 수행되는 시간

• 시간 복잡도가 낮다 -> 입력-출력까지의 시간이 짧다고 생각하자
  시간 복잡도가 높다 -> 입력-출력까지의 시간이 길게 걸린다

점진적 표기법

표기법에는 3가지가 있다.

1. 오메가 표기법(Ω) : 제일 좋은 경우

2. 세타 표기법 (Θ) : 평균적인 경우

3. 빅오 표기법 (O) : 제일 나쁜 경우

출처: https://www.bigocheatsheet.com/

시간 복잡도 계산

시간 복잡도는 일반적으로 빅오 표기법으로 나타냅니다.

연산 횟수가 다항식으로 표현될 경우, 최고차항을 제외한 모든 항과 최고차항의 계수를 제외시켜 나타냅니다.

예를 들어 입력 크기가 n이라고 했을 때 다음과 같이 표기합니다.

$T(n) = n^2 + 2n + 3 = O(n^2)$ : 최고차항만 나타냄.
$T(n) = 4n = O(n)$ : 최고차항의 계수는 제외함.

예제

	static int func(int n) {
		int sum = 0; // 대입: 1
		int i = 0; // 대입: 1

		for(i = 0; i < n; i++) { // 반복 수행: n, 대입: 1
			sum += i; // 대입: n
		}
		for(i = 0; i < n; i++) { //반복 수행: n, 대입: 1
			sum += i; //대입: n
		}
		return sum;
	}

시간 복잡도는 4n + 5 따라서 $O(n)$ 으로 표기한다.

$O(n^2)$

---

반복문 안에 반복문이 있는 경우

static void func(int[] arr) {
		for(int i = 0; i < arr.length; i++) {
			for(int j = 1; j < arr.length; j++) {
				System.out.println(arr[i] + arr[j]);
			}
		}
	}

$O(log n)$

---

i의 증가율이 2배씩 증가할 때

static void func(int n) {
		int i = 0;
		
		while(i < n) {
			System.out.println(i);
			i *= 2;
		}
	}

$O(n*logn)$

---

$O(n)$ 과 $O(logn)$이 중첩된 형태

	static void func(int n) {

		for(int j = 0; j < n; j++) {

			int i = 0;

			while(i < n) {
				System.out.printf("%d %d", i, j);
				i *= 2;
			}			
		}
	}