exponential
-
Big-O 표기법Algorithm 2022. 5. 2. 00:02
Big-O 표기법 알고리즘을 시간(초단위)으로 표현을 하기에는 하드웨어에 따라서 더 빠를 수도 느릴 수도 있기 때문에 비교를 할 수가 없습니다. 그렇기 때문에 알고리즘의 성능을 수학적으로 표현하기 위한 표기법이 필요했고, 완료까지 걸리는 절차(STEPS)의 수를 속도로 보고 이를 Big-O 표기법을 사용해서 표기합니다. 예를 들어 Linear Search는 한 번에 하나씩 찾기 때문에 10개의 아이템이 있으면 10번의 스탭을 사용하고, 20개가 있으면 20번의 스탭을 거쳐야 찾을 수 있습니다. 이것은 입력되는 데이터의 사이즈 인 Input size가 N개이면 N번의 Step이 요구된다는 뜻이며, 그렇기 때문에 Linear Serarch의 시간 복잡도는 O(N)이 된다고 볼 수 있습니다. 이렇게 Big-O..