💡 알고리즘
- 고대 페르시아의 수학자 알콰리즈미(Al-Khwarizmi)에서 유래
- 문제를 해결하기 위한 여러 동작들의 모임
💡 알고리즘의 조건
- 정밀성: 변하지 않는 명확한 작업 단계를 가짐
- 유일성: 각 단계마다 명확한 다음 단계를 가짐
- 입력: 정의된 입력을 받아들임
- 출력: 답으로 출력을 내보냄
- 유한성: 특정 수의 작업 이후에 정지
- 일반성: 정의된 입력들에 일반적으로 적용
💡 시간복잡도 Time Complexity
- O(N) 빅-오 표기법: Worst Case
- θ(N) 빅-세타 표기법: Average Case
- Ω(N) 빅-오메가 표기법: Best Case
=>Big-Oh 표기법은 연산의 최대 횟수에서 최고차항의 차수만을 표하며 가장 널리 사용된다.
- O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!) < O(nⁿ)
![](https://velog.velcdn.com/images%2Fkji990607%2Fpost%2F444c24d3-23e4-48be-9cf8-5aac410e6b7a%2Fimage.png)
- O(n log n): 선형로그. 힙 정렬, 병합 정렬, 퀵 정렬의 average case
- O(n²): 버블 정렬, 삽입 정렬, 퀵 정렬의 worst case
참고링크