시간복잡도와 공간복잡도

시간복잡도 (Time Complexity)

• 입력 데이터가 특정 알고리즘을 거쳐 결과가 나오는데 걸리는 시간을 의미한다.
  • 시간은 정확히 몇 초가 걸린다는 의미가 아닌 데이터의 증가에 따른 시간(연산속도)의 증가 정도를 말한다.
• 시간복잡도는 대입연산, 사칙연산, 비교구문, 함수호출등의 연산을 기준으로 계산한다.
• 시간복잡도는 최선의 경우, 평균의 경우, 최악의 경우로 나뉘어진다.

빅-오(Big-O) 표기법

• 시간복잡도를 표현한 다항식에서 최고차항의 차수가 빅-오가 된다.
• 100n^3 + 999999n^2 + 10에서 빅-오 표기법을 이용하면 O(n^3)이 된다. n의 값이 크면 클수록 100n^3과 999999n^2의 차이가 발생하게 된다. 999999n^2도 충분히 큰 수이지만 제외한 이유는 데이터의 증가에 따른 시간의 증가 정도를 표현하기 때문이다.

출처 및 참고사이트

• 참고사이트
• 윤성우의 열혈 자료구조

공간복잡도 (Space Complexity)

• 알고리즘을 수행할 때 필요한 메모리의 총량을 의미한다.
• Space Complexity = Auxiliary Space + Input Size Space
• Auxiliary Space는 알고리즘을 실행하면서 필요한 임시변수 등을 의미한다.
• Input Size는 알고리즘에 전달되는 파라미터 값이나 문제해결을 하는데 사용되는 변수를 의미한다.

프로그램의 메모리 사용

• 프로그램이 메모리를 사용할 때는 아래와 같다.
• 프로그램의 명령어들
  • 컴파일러에 의해 컴파일된 명령어 mov, sub, …
• 환경적인 부분
  • A함수에서 B함수를 호출하면 A함수의 다음 위치 및 A함수에서 사용된 변수값들을 스택에 PUSH하고 B함수가 종료되면 A함수의 변수값들을 다시 POP해서 원래 내용대로 돌아오는 행위들
• 데이터 공간
  • 변수 또는 상수의 메모리 양
• 알고리즘에서 공간복잡도를 구할때는 보통 데이터 공간을 이용해 계산한다.

출처 및 참고사이트

• 참고사이트1
• 참고사이트2