프로그램 시간의 복잡도에 관한 작은 문제

오늘 수업 후 문제는 다음과 같은 순서가 있다

 1 // 1.10    .cpp :              。

 2 //

 3 

 4 #include <iostream>

 5 

 6 using namespace std;

 7 int main    ()

 8 {

 9     int n=100;

10     int k=0;

11     int a[200];

12     int t=0;

13     int count=0;

14     for (int i=1; i<=n-1; i++)

15     {

16         k=i;

17         for(int j=i+1; j<n; j++)

18         {

19             if (a[j]>a[j+1])

20             {

21                 k=j;

22 

23                 

24             }

25             cout<<i<<"\t"<<j<<"\t"<<count++<<endl;

26         }

27         t=a[k];

28         a[k]=a[i];

29         a[i]=t;

30     }

31     cout<<double(count)/(n*n)<<endl;

32 

33     return 0;

34 }

책에서 제시한 답안의 복잡도는 O(n)이다. 내 느낌은 O(n2)인 것 같다. 그래서 원문 끝에 31의 디스플레이 출력 문구를 추가하여 검증했다. 여러 번 시도한 후에 답안이 확실히 가까워졌다(n2)/2를 발견했다. 그래서 개인적인 느낌으로 책에 답안이 틀린 것 같다. 가르쳐 달라.
나는 문제가if문장이 실행될 때 확률이 있다는 것을 발견했다. 나는 계산하지 않았지만, 어떻게 계산해야 하는가를 발견했다.아직 두서가 없다.