시간 복잡도
빅오 표기법
시간 복잡도란 문제를 해결하는 데 걸리는 시간과 입력의 함수관계를 가리킨다. 보통 빅오 표기법으로 시간복잡도를 나타낸다.빅오 표기법이란 입력 범위 n을 기준으로 해서 로직이 몇 번 반복되는지 나타내는 것이다. 빅오 표기법은 가장 영향을 많이 끼치는 항의 상수 인자를 빼고 나머지 항은 다 없앴다. 입력 크기가 커질수록 연산량이 가장 많이 커지는 항 외 나머지는 그것에 비해 미미하기 때문이다.
시간 복잡도의 속도 비교
O(n^2) 보다는 O(n), O(n) 보다는 O(1)을 지향해야 한다. 이러한 시간복잡도는 바로 효율적인 코드로 개선하는 데 쓰이는 척도가 된다.
공간 복잡도
공간복잡도는 프로그램을 실행했을 때 필요로 하는 자원 공간의 양을 의미한다. 정적으로 선언된 변수 말고도 동적으로 재귀적인 함수로 인해 공간을 계속해서 필요로 하는 경우도 포함된다.
블로그 이전했습니다