목록점근표기법 (1)

포시코딩

시간복잡도의 점근 표기법 (Big-O, Big-Ω)

점근 표기법의 종류에는 빅오(Big-O) 표기법과, 빅 오메가(Big-Ω) 표기법이 있다. 빅오 표기법 - 최악의 성능이 나올 때 어느 정도의 연산량이 걸릴 것인지 ex) O(N) 빅오메가 표기법 - 최선의 성능이 나올 때 어느 정도의 연산량이 걸릴 것인지 ex) Ω(1) for element in array: # array 의 길이만큼 아래 연산이 실행 if number == element: # 비교 연산 1번 실행 return True return False 다음과 같은 함수가 있을 때 이 함수의 시간복잡도는 N * 1 인 것을 알 수 있다. 만약 array = [3, 5, 6, 1, 2, 4]에 대해 3을 찾는다면 1번의 연산만에 답을 찾을 수 있을 것이다. 하지만 array = [5, 6, 1, ..
자료구조알고리즘/이론 2022. 11. 22. 20:30
이전 Prev 1 Next 다음