복잡도
시간 복잡도
C++의 기본
메인 함수를 중심으로 돌아가므로 메인 함수 하나를 무조건 만들어야 한다. 이후 컴파일이 시작되면 전역변수 초기화, 라이브러리 import 등의 작업이 일어나고, 메인 함수에 얽혀 있는 함수들이 작동된다. 그리고 메인 함수기 0을 리턴하며 프로세스가 종료된다.
빅오 표기법
시간 복잡도란 문제를 해결하는 데 걸리는 시간과 입력의 함수 관계를 가리킨다. 어떠한 알고리즘의 로직이 얼마나 오랜시간이 걸리는지를 나타내는 데 쓰이며, 보통 빅오 표기법으로 나타낸다.
빅오 표기법이란 입력 범위 n을 기준으로 해서 로직이 몇번 반복되는지 나타내는 것인데, 앞서 말한 코드의 시간 복잡도를 빅오 표기법으로 나타내면 0이 된다.
존재이유
효율적인 코드로 개선하는데 쓰이는 척도가 된다. 버튼을 누르고 화면이 나타나는데 이 로직이 0의 시간 복잡도를 가지고 9초가 걸린다고 해보자. 이를 0의 시간 복잡도를 가지는 알고리즘으로 개선한다면 3초가 걸리게 된다.
공간 복잡도
프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양. 정적변수로 선언돤 것 말고도 동적으로 재귀적인 함수로 인해 공간이 필요할 경우도 포함.
자료 구조에서의 시간 복잡도
자료 구조 평균 시간 복잡도
자료 구조 / 접근 / 탐색 / 삽입 / 삭제
배열 / O(n) / O / O / O
스택 / O / O / O(1) / O(1)
큐 / O / O / O(1) / O(1)
이중 연결 리스트 / O / O / O(1) / O(1)
해시 테이블 / O(1) / O(1) / O(1) / O(1)
이진 탐색 트리 / O(logn) / O / O / O
AVL 트리/ O / O / O / O
레드 블랙 트리 / O / O / O / O
선형 자료 구조
