오늘한일
자료구조 / 알고리즘의 시간복잡도 개념을 알게 되었고,
Greed 알고리즘, Dynamic Programming의 개념을 알게되었다.
Achievement goals
- 알고리즘이 무엇인지 설명할 수 있다.
- 시간복잡도에 대해서 설명할 수 있다.
알고리즘 (Algorithm)
코드 스테이츠 에서 말하는 알고리즘은 '문제를 어떤 식으로 푸는 것이 최선인가'로 정의 한다.
내가 이해한대로 설명해보자면, 앞서 다룬 DFS BFS는 그래프를 순회 하는 목적은 같으나 방법이 다르다.
어떠한 문제에 대해서 깊게 파악하고 다양한 문제 해결 방식중 더 효율적인 방식을 고민하고
최선의 전략을 세우는 연습인것같다.
시간 복잡도 (Time Complexity)
문제를 풀때 좀더 효율적인 방법을 고민한다는것은 시간 복잡도를 고민한다는 것과 같다.
시간복잡도는 입력값의 증가/감소함에 따라 시간이 얼마만큼 비례하여 증가/감소하는가?로 말할 수 있고,
앞서 문제 해결 방식중 더 효율적인 방식을 고민하는것은
입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘을 구성한다고 볼 수 있다.
오늘 배운 시간 복잡도는 가장 흔히 사용되는 Big-O 표기법이다.
O(1) : 데이터의 크기에 상관없이 언제나 일정한 시간이 걸리는 알고리즘을 말한다.
function O_1_algorithm(arr, index) {
return arr[index];
}
O(n) : 데이터 크기가 증가함에 따라 시간 또한 같은 비율로 증가하는 알고리즘을 말한다.
function O_n_algorithm(n) {
for (let i = 0; i < n; i++) {
// do something for 1 second
}
}O(log n) : Big-O표기법중 O(1) 다음으로 빠른 시간 복잡도이며, 대표적으로 이진 탐색 알고리즘이 있다.
이진 탐색은 한번 처리가 진행될때마다 검색해야하는 데이터의 양이 절반씩 줄어드는 알고리즘을 말한다.
O(n^2) : 입력값이 증가함에 따라 시간이 그의 제곱수의 비율로 증가하는 알고리즘을 말한다.
function O_quadratic_algorithm(n) {
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
// do something for 1 second
}
}
}O(2^n) : Big-O표기법 중 가장 느린 시간 복잡도를 가진다. n의2승과 헷갈릴 수 있는데 둘은 너무나 다른 알고리즘이다. 입력한 데이터가 커질수록 시간이 2의 제곱만큼 늘어나는 알고리즘이다.
가장 대표적으로 재귀로 구현하는 피보나치 수열이 있고, n을 100이상만 두어도 평생 결과를 반환받지 못한다고 한다.
function fibonacci(n) {
if (n <= 1) {
return 1;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}참고사이트
