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

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

 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문장이 실행될 때 확률이 있다는 것을 발견했다. 나는 계산하지 않았지만, 어떻게 계산해야 하는가를 발견했다.아직 두서가 없다.

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

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

오늘 수업 후 문제는 다음과 같은 순서가 있다 책에서 제시한 답안의 복잡도는 O(n)이다. 내 느낌은 O(n2)인 것 같다. 그래서 원문 끝에 31의 디스플레이 출력 문구를 추가하여 검증했다. 여러 번 시도한 후에 ...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

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

좋은 웹페이지 즐겨찾기