정렬 알고리즘에 걸리는 반복 횟수를 비교하기 전에 단계를 포함합니까?

Question

임마는 공백이 조금 있습니다. 알고리즘을 완료하는 데 걸리는 단계 수를 계산할 때 비교가 수행되지 않은 단계를 포함해야합니까? 예를 들어

: 5,3,7

및 종류에 그것을 거품을 수행하면 목록이있는 경우

. 그것은 것;

1) 5과 3을 비교하고 5>3으로 바꾸십시오. 목록은 현재 3,5,7

2) 5과 7을 비교하지 않고 5<7으로 비교하십시오. 목록은 현재 3,5,7

3) 예상대로 변경되지 않고 3과 5입니다. 목록은 여전히 ​​3,5,7

4) 예상대로 변경되지 않고 5과 7을 비교하십시오. 목록은 여전히 ​​3,5,7

이니 반복 횟수는 4 또는 5가 될 것입니까? ... 아니면 완전히 잘못 됐어?

덕분에

Answer 1

: 상기 내용을 토대로

procedure bubbleSort(A : list of sortable items) 
    repeat  
    swapped = false 
    for i = 1 to length(A) - 1 inclusive do: 
     // this is the start of an iteration 
     if A[i-1] > A[i] then 
     swap(A[i-1], A[i]) 
     swapped = true 
     end if 
     // this is the end of an iteration 
    end for 
    until not swapped 
end procedure 

(Wikipedia에서 촬영), 우리가 실제로있을 때 우리는 반복 계산 있음을 쉽게 알 수 있어야한다 비교하고.

그래서 4 번 반복됩니다.

---

는 전문적으로, 당신은 또한 당신에게 매우 다른 결과를 줄 것이다 repeat ... until 루프의 관점에서 반복에 대해 이야기 할 수있다.

'단계'는 분명히 많은 작은 부분으로 나눌 수 있습니다.

위와 비슷한 모호성 때문에 big-O notation을 사용하는 경향이 있습니다. 이는 실제로 알고리즘 실행 시간의 증가 속도를 제공합니다.

Answer 2

당신은 4 반복을 수행했습니다. 걸음이 아직 수행하지 않은 경우 반복의 수가 4

Algorithm 

//... some precondition steps 

iteration(for...) {  < 
    //...      < iteration steps 
}       < 

Answer 3

IMHO이 시점에서, 이유는 스텝 카운트 = 0으로 한 단계를 수행 한 후, 걸음 수 = 1 I이며 진정으로 당신이 4 단계를 수행하는 것이 5 단계로 간주된다는 점을 어떻게 생각하는지 모르겠다.

어쨌든, 일반적으로 O (f (n))로 분석된다는 것을 기억해야한다. + + 상수 ie + -1 또는 + -100은 단순히 떨어집니다. 그것은 때로는 코드에 대한 생각 /보고하는 데 도움이