시간과 공간
프로그램을 실행하기 위해서는 시간과 메모리가 필요하다. 같은 기능을 수행하는 프로그램 둘이 있을 때 시간과 메모리를 덜 소모할수록 효율적인 프로그램이다.
복잡도
복잡도란 작성한 알고리즘이 효율적인지 시간, 공간적으로 효율적인지를 판단하는 기준이다. 알고리즘의 효율성을 정량화한다. 시간복잡도는 알고리즘의 실행시간을 정량화한 것이다. 공간복잡도는 알고리즘의 실행에 필요한 메모리량을 정량화한 것이다.
빅오표기법
빅오표기법은 알고리즘의 복잡도를 표기하는 방법 중에 하나로 최악의 경우의 상관관계를 표현한다. 입력 데이터 대비 함수를 실행하는 데에 필요한 비용(시간, 공간)의 상관관계를 수식의 최고차항으로 표현한다.
그래프는 시간복잡도를 표현한 것이다. 최고차항이 커질수록 동일 입력 데이터 대비 소요되는 시간이 급격하게 증가한다.
복잡도가 필요한 이유
복잡도를 사용하면 코드의 성능을 평가할 수 있다. 이는 더욱 효율적인 코드를 작성하는 데에 도움이 된다.