빅오

복잡도란 알고리즘의 성능을 나타내는 척도이며 시간복잡도(Time complexity)는 특정한 크기의 입력에 대해 알고리즘이 시간을 얼마나 소요하는지를 나타낸다. 시간복잡도를 표현할 때는 일반적으로 빅오표기법을 사용한다. 알고리즘 문제를 풀 때 단순히 '복잡도'라고 한다면 시간복잡도를 의미한다. 코딩 테스트에서의 시간제한은 시간내에 문제를 풀어야 한다는 제한보다는 작성한 프로그램이 모든 입력을 받아서 이를 실행하고 결과를 출력하는 데 까지 소요되는 시간의 제한을 의미한다. 시간복잡도를 계산할 때 N개의 데이터에 대한 연산의 횟수에 의존하는 경우가 많다. 아래의 예시들을 통해서 시간복잡도를 이해해본다. 더보기 예시1) 위의 예시는 N=5의 데이터의 총합을 계산하는 코드이다. 이 때 연산횟수는 데이터의 개수..

복잡도란 알고리즘의 성능을 나타내는 척도이다. 복잡도에는 시간복잡도(Time Complexity)와 공간복잡도(Space Complexity)가 있다. 시간복잡도는 특정한 크기의 입력에 대해 알고리즘이 시간을 얼마나 소요하는지를 나타내고 공간복잡도는 특정한 크기의 입력에 대해 알고리즘이 메모리를 얼마나 차지하는지를 나타낸다. 일반적으로 적은 시간을 소요하고, 적은 메모리를 차지하는 것이 좋은 알고리즘이라는 것은 자명한 사실이다. 복잡도를 표기하는 방법에는 여러가지 방법이 있다. 빅오(Big-O)표기법 빅오메가(Ω)표기법 빅세타(Θ)표기법 빅오(Big-O)표기법 먼저 빅오(Big-O)표기법이란 쉽게 말해 함수의 상한(upper-bound)만을 고려하는 표기법이다. 즉, 가장 빠르게 증가하는 항만을 고려하는..