대문자 O표기법: 계산 복잡도 표현
출처: 모두의 알고리즘 with 파이썬 어떤 알고리즘이 문제를 풀기 위해 해야 하는 계산이 얼마나 복잡한지 나타낸 정도를 '계산 복잡도'라고 한다. 계산 복잡도를 표현하는 방법에는 여러 가지가 있는데, 그 중 대문자 O 표기법을 가장 많이 사용한다. 이 대문자 O표기법을 '빅 오' 표기법 이라고도 부른다. 예를 들어 1부터 n까지의 자연수의 합을 구하는 문제는 1부터 n까지 덧셈 연산을 n번 하는 방법이 있을 것이고, 1과 n을 더한 후 2로 나누고 n을 곱하여 구하는 방법이 있을 것이다. 예시에서 첫 번째 알고리즘처럼 입력크기 n에 대해서 덧셈을 n번 해야 하는 문제의 계산 복잡도를 O(n)이라고 표현한다. 필요한 계산 횟수가 입력 크기에 '정비례'할 때는 O(n)이라고 표현한다. 그러면 입력 크기 n..
beginner/파이썬 알고리즘
2019. 7. 17. 01:43