큰 O 작업 수

Question

각 코드 줄에서 수행 할 작업 수는 어떻게 계산합니까?

예.

Algorithm find2D (A,x) 
    arrLength = A.length 
    for j <- 1 to arrLength – 1 do 
     for k <- 1 to arrLength – 1 do 
       if A[j][k] = x then 
        return true 
      increment k 
    increment j 
return false 

나는이 의사 코드를 생각해 냈습니다. 따라서 코드의 각 줄에 필요한 작업 수를 계산하는 방법을 잘 모르겠습니다.

j를 설정해야하기 때문에 첫 번째 루프와 마찬가지로 1 + n 연산이 될 것입니다. j를 arrLength - 1과 비교하면 n-1 번 반복됩니다. 그러면 n-1 + 1 + 1이됩니다. 이것은 n + 1 연산입니다.

그래서 두 번째 루프의 경우 중첩되어 있어도 똑같습니다.

나는 약간의 조작이 얼마나 될지에 대해 A[j][k] = x 비교에서 다소 혼란 스럽습니다.

감사합니다. 만약 어레이의 각 소자 위에, (로그 곱하여 반복적 둘로 어레이 나눌 때마다 N

곱 루프마다 기록

:

Answer 1

Big-Oh은 점근 적이므로 "1 + n"의 "1"에 신경 쓰지 않아야합니다.

해당 코드의 Big-Oh 분류를 찾으려면 두 개의 루프가 있고 하나는 다른 루프 내부에 중첩되어 있고 각 루프는 요소 당 일정한 수의 연산을 수행한다고 생각하면됩니다. 그런 다음 내부 루프는 O (n)이고 외부 루프는 내부 ​​루프를 n 번 실행하므로 외부 루프는 O (n^2)입니다. 그러면 전체 함수는 O (c + n^2)입니다. 여기서 c는 외부 루프를 둘러싼 코드의 일정한 연산 수입니다. Big-Oh가 점근 적이므로 c가 사라지고 함수는 O (n^2)입니다.

코드에서 수행하는 정확한 작업 수를 계산하려면 사용중인 abstract machine을 설정해야 할 수 있습니다.

희망이 도움이됩니다.

Answer 2

일반적인 어림짐작이있다 N)

전체 배열에 두 개의 중첩 루프가 있으므로 O (N^2)입니다.

상수 계수를 계산하는 것은 까다 롭고 언어, 컴파일러 및 하드웨어의 세부 사항에 따라 다릅니다. 기본적으로는 경험적으로 그렇게해야합니다.

Answer 3

큰 오에서는 가장 자주 발생하는 작업과 가장 자주 발생하는 작업을 선택해야합니다. 이 경우 두 루프 내부의 비교입니다. 반복 할 비교 루프의 수를 계산할 필요가 없습니다. 가장 안쪽 부분이 최악의 경우에 몇 번 실행되는지 계산하면됩니다. 외부 루프에 대해서는 n-1이고, 내부 루프에 대해서는 각각 n-1이며, 이는 O(n^2)입니다.