2주동안 데이터 구조와 알고리즘에 대한 파트였는데, 코스를 하면서 가장 힘들고 포기하고 싶은 생각이 많이 들었다...
처음 들어보는 내용과 머리를 상당히 써야지 풀리는 문제들만 가득했으니 ..
알고리즘 문제를 풀지못하고 풀이를 봐도 이해하기가 상당히 어렵더라 ㅎㅎ..
풀이와 같은 방법으로 어떻게 생각하는것일까....
넋두리는 여기까지 ㅋㅋ 🤣
알고리즘 초반부에 배운 시간복잡도에 대해 복습겸 블로깅을 해보아야지!
1. 시간복잡도
시간복잡도? 이것은 또 무엇인가 ...
알고리즘 문제를 풀때 문제 해결을 위한 시간(연산)의 횟수를 의미한다.
클래스에서 설명하길
입력값의 증가/감소함에 따라 시간이 얼마만큼 비례하여 증가/감소하는가?
결국 문제를 해결할 때 연산의 시간을 최소화하여 효율적으로 시간을 사용하기 위해서 만들어진 것 같다. (같은 문제라도 어떤 방식을 쓰느냐에 따라 달리지기 마련이니..)
1.1 Big-O 표기법
- Big-O (최악)
- Big-Ω (최선)
- Big-θ (중간,평균)
입력값의 증가에 따라 시간 복잡도가 얼마나 증가하는지 표기하는 방법!
1.2 Big-O 표기법의 종류
O(1) : constant complexity
-> 입력값이 증가해도 시간은 늘어나지 않음을 의미한다! , 즉시 출력값을 얻어 낼 수있음!
funciton O_1(arr, index){
return arr[index]
}
let arr = [1,2,3,4,5];
let index = 1;
let result = O_1(arr, index);
console.log(result) //2;
// 입력값이 커져도 인덱스번호에 해당하는 값만 출력하면 되기때문에
// 알고리즘 연산시간에 영향이 없다! O(n) : linear complexity
-> 입력값의 증가에 맞춰 시간도 같은비율로 증가함!
function O_n(n) {
for (let i = 0; i < n; i++) {
}
}
function another_O_n_(n) {
for (let i = 0; i < 2n; i++) {
}
}
// 반복문의 크기에 따라 연산시간의 증가도 같은 비율로 늘어난다.
아래 2n의 경우는 2n만큼 증가하지만
Big-O 표기법에는 앞의 계수는 제거하고 O(n)으로 표기함.
(수업때 들은바로 아주 멀리서 보면 그 증가의 그래프 모양이 하나의 직선으로 보인다고 해서 계수를 지운다고 들었다.)
O(log n) : logarithmic complexity
O(log n)는 앞에서 배운 BST(이진트리탐색)을 예로 들면서 설명했다.
루트보다 작으면 왼쪽으로, 크면 오른쪽으로 이동하여 탐색하기 때문에 선택하지 않은 절반은 자동으로 버릴 수 있어서 입력값이 커지더라도 시간의 증가가 크지 않다!!
그래서 Big-O표기법중 O(1) 다음으로 빠른 시간 복잡도를 가진다.
BST만 이해하면 쉽게 이해되는 시간복잡도!
O(n²) : quadratic complexity
-> 입력값이 증가하는데 그 시간이 제곱으로 증가는것을 의미!
function O_quadratic(n) {
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
// do something for 1 second
}
}
}반복문안의 반복문을 생각하면 이해하기가 쉽다. n*n 만큼 반복문을 돌아야지 끝!
(위의 예시는 n^2)
반복문에 3번 중첩되어 있다면 n^3, 5번이면 n^5
하지만 표기법은 동일하게 O(n²); 계수는 삭제
O(2n) : exponential complexity
O(2n) 설명은 전부 다 피보나치 수열로 해주더라 ㅎ..
function fibonacci(n) {
if (n <= 1) {
return 1;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}-> Big-O표기법 중 가장 느린 시간 복잡도를 가진다.
구현한 알고리즘의 시간 복잡도가 O(2n)이라면 다른방법을 생각하는것이 좋다고한다. (느리니깐 ㅋ)
마무리
시간복잡도를 배우기전까지는 그냥 내가 작성한 코드로 문제가 해결되면 끝인줄 알았다. ㅎㅎ 이제는 시간복잡도를 생각해서 더 효율적인 코드를 짜야한다는것을 알게 되었다...
생각없이 코드를 짰다가는 코드테스트는 통과할수 없겠지..
으... 다음 작성할 내용은 Greedy Algorithm, Dynamic Programming .... 수업을 한번더 듣고 와야겠다 ㅎ..😩
(다행히 나만 어려운건 아니라고해서 약간의 안도? ㅋㅋ)
