[Algorithm] 알고리즘이란, Big-O
Algorithm
알고리즘 - '문제를 어떤 식으로 푸는 것이 최선인가'
1. 문제 이해하기
- 제한사항 및 주의사항 꼼꼼히 읽기.
2. 문제에 대한 전략 세우기
- suedo code 짜기
- 그림 그리기
3. 코드 작성하기
- 전략을 코드로 옮기기
- 최적화 해보기
Time Complexity
입력값의 증가/감소에 따라 시간이 얼마만큼 비례하여 증가/감소하는가?
효율적인 알고리즘 - 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘
Big-O
시간 복잡도를 표현하는 방법
Big-O (최악)
Big-Ω (최선)
Big-θ (평균)
Big-O가 자주 사용되는 이유는 항상 최악의 경우를 대비하여 알고리즘을 설계해야 문제가 발생할 경우 쉽게 찾을 수 있다.
Big-O 표기의 종류
Fast -> Slow
O(1)
Constant complexity.
입력값이 증가해도 시간이 늘어나지 않음.
O(n)
Linear complexity
입력값이 증가함에 따라 시간 또한 같은 비율로 증가.
입력값이 커지면 커질수록 계수의 영향력이 줄어들기 때문에 , 등은 으로 표기.
O(log n)
Logarithmic complexity
Binary Search Tree 는 노드를 이동할 때 마다 경우의 수가 절반으로 줄어든다.
Binary Search 또한 중간값을 찾을 때 마다 범위가 반으로 줄어든다.
O(n^2)
Quadratic complexity
입력값이 증가함에 따라 시간이 그 제곱수의 비율로 증가
, 등을 모두 으로 표기.
예시)
function quadratic_algorithm(n) {
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
// ...
}
}
}
O(2^n)
Exponential complexity
Big-O 표기법 중 가장 느리다.
입력값이 증가할 때 마다 시간이 두배로 증가한다.
지수 복잡도를 가진 알고리즘은 다시 생각해봐야 한다.
예시) 재귀로 구현한 피보나치 수열
function fibonacci(n) {
if (n <= 1)
return 1;
return fibonacci(n - 1) + fibonacci(n - 2);
}
Advanced
코딩테스트는 정확한 값을 제한된 시간 내에 반환하는 프로그램을 작성해야 한다.
데이터가 클 때는 O(n) 혹은 O(log n) 정도로 예측해서 문제를 풀어보고, 주어진 데이터가 작을 때는 시간복잡도가 크더라도 문제 풀이에 집중하는 것이 좋다.
데이터 크기 제한 | 예상 시간 복잡도 |
---|---|
n ≤ 1,000,000 | O(n), O(log n) |
n ≤ 10,000 | O(n^2) |
n ≤ 500 | O(n^3) |
Tips
N^2 에서 줄일 때 -> BS, DP (Memo), 정렬
기본: 완전탐색 (exhaustive search)
- DFS/BFS, 순열/조합(부분집합) => coding test 70% 이상 cover
그래프류, 최단거리(다익스트라, 벨만포드, 플로이드 와샬)
sort 류 (sort 는 요즘 잘 안나옴)
공간복잡도
JS 에서 데이터 1천만개는 8MB
그래프류
N 이 1000개 -> 1000 x 1000 < 1천만
N 이 10000개 -> 이차원 행렬 쓰면 안됨. 10000^2 > 1천만
문제가 풀리기만 하면 최적화는 필요없다 -> over engineering, overkill
책
누워서 읽는 알고리즘, 누워서 읽는 퍼즐북, 즐거운 논리, Nine altorithms taht changed the future
Author And Source
이 문제에 관하여([Algorithm] 알고리즘이란, Big-O), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jhoryong/Algorithm-알고리즘-Big-O저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)