점근표기법
-
[파이썬 기초] 알고리즘의 개념 / 코딩 연습 - 시간 복잡도프로그래밍 2021. 4. 1. 22:21
# 시간 복잡도(Time complexity) : 데이터가 많아질수록 알고리즘이 답을 찾는 데 걸리는 시간이 얼마나 급격히 증가하는지를 나타내는 개념. 시간 복잡도가 작은 알고리즘이 더 빠른 알고리즘이다. # 점근표기법(Big-O Notation) 시간 복잡도를 근사치로 표현하는 방법으로, 해당 알고리즘 내에서 답을 가장 늦게 찾을 경우(Worst cast)의 시간 복잡도를 빅 오 표현법이라 한다. 소요 시간이 20n + 40인 알고리즘의 점근 표기법(Big-O)은 O(n)이 될 것이다. 각 소요시간(예시)에 따른 점근 표기법은 다음과 같다. n이 크지 않은 숫자라면 알고리즘이 좋지 않아도 상관없으나, n이 크면 어떤 시간 복잡도를 갖고 있느냐에 따라 걸리는 시간이 기하급수적으로 증가하기 때문에 알고리즘..