알고리즘의 시간 복잡도, Big-O

알고리즘이란

• 어떤 목적을 달성하거나 결과물을 만들어내기 위해 거쳐야 하는 일련의 과정들을 의미
• 시간 복잡도가 낮은 알고리즘을 선택해서 사용

알고리즘의 실행시간 

• 입력값의 크기에 따라 알고리즘의 실행시간을 검증
• 입력값의 크기에 따른 함수의 증가량 (=성장률)에 집중할 수 있는데 점근적 표기법 (Asymptotic notation)으로 검증 

점근적 표기법 -> 시간 복잡도

• 최상의 경우 :오메가 표기법  (Big-Ω Notation)
• 평균의 경우: 세타 표기법 (Big-θ Notation)
• 최악의 경우: 빅오 표기법 (Big-O Notation)

-최악의 경우인 빅오를 사용하여 알고리즘이 최악일 경우를 판단하여 예측

 

 

It measures of memory complexity in most cases is completely independent to the measure of time complexity.

 For computer algorithms, it is important to know how the algorithm will manage both of these complexities to decide the quality of the algorithm. 

 

 

O(1): 상수 (Constant time)

O(1) means constant average memory use, regardless the size of your input

-> (어떤 용량의 input을 넣더라도 메모리는 일정, 같은 시간동안 처리)

O(1) 예시

O(n): 선형 (Linear time)

O(n) means if you have n element you are processing, your average memory need grows linear

-> (Input이 많으면 많을 수록, 처리 시간 or 메모리 사용이 선형적으로 증가한다)

O(n) 예시

O(n^2): Square

반복문 두번 있는 케이스

O(n^2) 예시

O(log n)

Input의 크기 n이 커질 때 연산 수가 logn에 비례해서 증가한 복잡도 표현

대표적인 예시) 오름차순 정렬된 배열의 이진 검색

O(log n) 예시

 

시간 복잡도 구하는 요령

하나의 루프를 사용하여 단일 요소 집합 반복 -> o(n)

컬렉션의 절반 이상을 반복 -> O(n/2) -> O(n)

두 개의 다른 루프를 사용하여 두 개의 개별 콜렉션을 반복할 경우 -> O(n+m) -> O(n)

중첩 루프 사용 O(n^2)

두개의 중첩루프를 사용하여 두개의 다른 콜렉션을 반복할 경우 -> O(n*m) -> O(n^2)

컬렉션 정렬을 사용하는 경우-> O(n*log(n))

 

복잡도 비교

O(1)<O(log n)<O(n) < O(n^2) < O(n^3) <O(2^n)

 

 

 

출처:https://blog.chulgil.me/algorithm/

알고리즘의 시간 복잡도와 Big-O 쉽게 이해하기

https://dingrr.com/blog/post/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%8B%9C%EA%B0%84%EB%B3%B5%EC%9E%A1%EB%8F%84-%EC%98%88%EC%A0%9C-15%EC%A2%85

[알고리즘] 시간복잡도 예제 15종 | 블로그 | 딩그르르