알고리즘의 연산 계산 방법

일부 알고리즘의 비용을 추정하는 다양한 방법이 있습니다. 작업 수를 사용하여 그 중 하나입니다. 다른 연산 중 하나를 선택하여 알고리즘의 시간 복잡도를 추정할 수 있습니다. 이것들은 더하기, 빼기 등과 같습니다. 이러한 연산이 얼마나 수행되었는지 확인해야 합니다. 이 방법의 성공 여부는 시간 복잡성의 대부분을 차지하는 작업을 식별하는 능력에 달려 있습니다.

크기가 n [0에서 n - 1]인 배열이 있다고 가정합니다. 우리의 알고리즘은 가장 큰 요소의 인덱스를 찾습니다. 배열의 각 요소 쌍 간에 수행되는 비교 작업의 수를 계산하여 비용을 추정할 수 있습니다. 우리는 하나의 작업만 선택할 것임을 기억해야 합니다. 이 알고리즘에는 반복 변수 i의 증가 또는 인덱스에 대한 값 할당 등과 같은 몇 가지 연산이 더 있습니다. 그러나 이 경우에는 고려되지 않습니다.

알고리즘

getMax(arr, n):
   index := 0
   max := arr[0]
   for i in range 1 to n - 1, do
      if arr[i] > max, then
         max := arr[i]
         index := i
      end if
   done
   return index

비용을 추정하기 위해 최대 시간 동안 수행되는 작업을 선택해야 합니다. 하나의 버블 정렬 알고리즘이 있고 스왑 작업을 계산한다고 가정합니다. 그런 다음 최대가 될 때를 염두에 두어야 합니다. 그러면 분석 중에 최대의 결과를 얻을 수 있습니다.