이것이 코딩테스트다

[알고리즘] 복잡도 / 빅오 표기법 기본 개념

1. 복잡도(Complexity) 시간 복잡도 : 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석 공간 복잡도 : 특정한 크기의 입력에 대해 알고리즘의 메모리 사용량 분석 동일한 기능을 수행하는 알고리즘이 있다면, 일반적으로 복잡도가 낮을 수록 좋은 알고리즘이다. 복잡도가 높다라는 것은 특정한 함수의 성능적인 측면에서 많은 시간을 소요하고, 많은 메모리의 자원을 먹는 것을 말한다. 2. 빅오 표기법(Big-O Notation) 가장 빠르게 증가하는 항(최고차항)을 고려하는 표기법 함수의 상한(최악의 수행시간)만을 나타내게 된다. ex ) 3N² + 5N + 100 의 경우, 빅오 표기법에서는 차수가 가장 큰 항만 남기므로 O(N²)으로 표현된다. 일반적으로 CPU 기반의 개인 컴퓨터나 채점용 컴퓨..