연결 리스트공부하다가 탐색 시간이 또 나왔는습니다.
탐색 시간이라는거 보면 O(n) 인데 제가 보기에는 그냥 영어 O 와 소괄호 n이여서 나중에 배우려고 좀 밀어뒀는데
새로운 자료구조 알고리즘 등을 배울때 자꾸 저게 나오니 번거로워도 먼저 공부하려고 합니다.
O(n) 시간복잡도를 나타내는 표기법인 빅 O 표기법
O : Order of 의 약자로 , 알고리즘의 성능을 설명
n : 입력 데이터의 크기 , 배열의 크기 ,리스트의 노드 수
그러면 배열의 크기가 5라면 O(5)
O(n)의 의미
알고리즘의 실행 시간이 데이터 크기(n)에 비례한다는 것을 의미.
입력 데이터가 커질수록 탐색하는 데 시간이 선형적으로 증가
10개의 요소와 100개의 요소 각각 10에 비례 , 100에 비례
O(1) - 상수 시간
항상 일정한시간에 실행 됨
배열의 첫번째 요소 접근시
O(n) - 선형 시간
입력 크기에 비례하여 실행 시간이 증가함
연결 리스트에서 특정 값을 찾기위해 모든 노드 순환시
-데이터 크기가 2배로 늘어나면, 탐색 시간도 2배로 늘어남
O(log n) - 로그 시간
입력 크기가 증가할때 , 탐색시간이 느리게 증가함.
주로 이진 탐색에서 사용
-데이터 크기가 2배로 늘어나도, 탐색 횟수는 1 증가
16개의 요소가 있는 배열에서 이진 탐색을 할 경우, 최대 4번의 비교(2^4 = 16)가 필요하며, 32개의 요소에서는 최대 5번의 비교(2^5 = 32)가 필요
O(n log n) - 선형 로그 시간
입력 크기가 증가할때 , 선형적으로 증가하며 로그 시간과 결합된복잡도
퀵 정렬 및 병합정렬에 사용
O(n^2) - 제곱 시간
입력 크기가 증가할 때, 실행 시간이 제곱으로 증가합니다. 주로 중첩 루프에서 발생
버블 정렬 , 선택 정렬에 사용
- 입력 크기(n)가 증가할 때, 실행 시간이 n의 제곱에 비례하여 증가하는 것을 의미
-데이터 크기가 2배로 늘어나면, 탐색 시간은 4배(2^2)로 늘어남
O(2^n) - 지수 시간
입력 크기가 증가할 때, 실행 시간이 지수적으로 증가합니다. 일반적으로 비효율적인 알고리즘에서 나타남.
-데이터 크기가 1 증가할 때마다 실행 시간이 두 배로 증가
-데이터 크기가 10일 경우 2^10 = 1024번의 호출이 발생할 수 있음.
O(n!) - 팩토리얼 시간
입력 크기가 증가할 때, 실행 시간이 팩토리얼로 증가합니다. 매우 비효율적!!
-입력 크기(n)가 증가할 때, 실행 시간이 n의 팩토리얼(1 × 2 × 3 × ... × n)에 비례하여 증가하는 것을 의미
- 데이터 크기가 1 증가할 때마다 실행 시간이 급격히 증가