알고리즘 의 시간 복잡 도 (계산 실례)

알고리즘 의 시간 복잡 도 (계산 실례)
 정의: 만약 에 한 문제 의 규모 가 n 이 라면 이 문 제 를 푸 는 특정한 알고리즘 에 필요 한 시간 은 T (n) 이 고 n 의 특정한 함수 T (n) 를 이 알고리즘 의 '시간 복잡성' 이 라 고 부 릅 니 다.
입력 량 n 이 점점 증가 할 때 시간 복잡성 의 극한 상황 을 알고리즘 의 '점 근 시간 복잡성' 이 라 고 부른다.
우 리 는 항상 대 O 표현법 으로 시간의 복잡성 을 나타 내 는데, 그것 이 어떤 알고리즘 의 시간 복잡성 이라는 것 을 주의해 야 한다.대 O 는 상계 가 있다 는 것 을 의미 할 뿐 정의 에 의 해 f (n) = O (n) 가 있다 면 f (n) = O (n ^ 2) 가 분명히 성립 되 고 상계 가 되 지만 상계 가 정확 한 것 은 아니 지만 사람들 이 표시 할 때 전 자 를 나타 내 는 습관 이 있다.
그 밖 에 한 문제 자체 에 도 복잡성 이 있다. 만약 에 특정한 알고리즘 의 복잡성 이 이 문제 의 복잡성 하계 에 이 르 렀 다 면 이런 알고리즘 이 가장 좋 은 알고리즘 이 라 고 할 수 있다.
"대기 법": 이 설명 에서 사용 하 는 기본 매개 변 수 는 n, 즉 문제 실례 의 규모 로 복잡성 이나 운행 시간 을 n 의 함수 로 표현 합 니 다.여기 서 'O' 는 헤비급 (order) 을 나타 낸다. 예 를 들 어 '2 분 검색 은 O (logn) 의 것' 이다. 즉, 'logn 헤비급 절 차 를 통 해 n 규모 의 배열 을 검색 해 야 한다' 는 것 이다.
이러한 점진 적 인 평 가 는 알고리즘 에 대한 이론 적 분석 과 대체적으로 비교 하 는 것 이 매우 가치 가 있 지만 실천 에서 세부 적 인 부분 도 차 이 를 초래 할 수 있다.예 를 들 어 낮은 부가 대가 의 O (n2) 알고리즘 은 n 이 비교적 작은 상황 에서 높 은 부가 대가 의 O (nlogn) 알고리즘 보다 더 빨리 실 행 될 수 있다.물론 n 이 충분 한 후에 비교적 느 린 상승 함 수 를 가 진 알고리즘 은 반드시 더욱 빨리 작 동 할 것 이다.
O(1)
Temp=i;i=j;j=temp;                    
상기 세 개의 단일 문장의 빈 도 는 모두 1 이 고 이 프로그램의 실행 시간 은 문제 규모 n 과 무관 한 상수 이다.알고리즘 의 시간 복잡 도 는 상수 단계 이 고 T (n) = O (1) 로 기록 합 니 다.만약 에 알고리즘 의 집행 시간 이 문제 규모 n 의 증가 에 따라 증가 하지 않 는 다 면 알고리즘 에 수천 개의 문구 가 있 더 라 도 그 집행 시간 은 비교적 큰 상수 에 불과 하 다.이런 알고리즘 의 시간 복잡 도 는 O (1) 이다.
O(n^2)
2.1 i 와 j 의 내용 교환
     sum=0；                 (한번)
     for(i=1;i<=n;i++)       (n 회)
        for (j = 1; j < = n; j + +) (n ^ 2 회)
         sum++；       (n ^ 2 회)
해: T (n) = 2n ^ 2 + n + 1 = O (n ^ 2)
2.2.   
    for (i=1;i    {
        y=y+1;         ①   
        for (j=0;j<=(2*n);j++)    
           x++;        ②      
    }         
문장 1 의 빈 도 는 n - 1 이다.
          문장 2 의 주파 수 는 (n - 1) * (2n + 1) = 2n ^ 2 - n - 1
          f(n)=2n^2-n-1+(n-1)=2n^2-2
          이 프로그램의 시간 복잡 도 T (n) = O (n ^ 2).         
O(n)      
                                                      
2.3.
    a=0;
    b=1;                      ①
    for (i=1;i<=n;i++) ②
    {  
       s=a+b;　　　　③
       b=a;　　　　　④  
       a=s;　　　　　⑤
    }
해: 문장 1 의 빈도: 2,        
           문장 2 의 빈도: n,        
          문장 3 의 빈도: n - 1,        
          문장 4 의 빈도: n - 1,    
          문장 5 의 빈도: n - 1,                                  
          T(n)=2+n+3(n-1)=4n-1=O(n).
                                                                                                 
O(log2n )
2.4.
     i=1;       ①
    while (i<=n)
       i=i*2; ②
해: 문장 1 의 빈 도 는 1,  
          설정 문 2 의 빈 도 는 f (n) 입 니 다.   예: 2 ^ f (n) < = n; f (n) < = log2n    
          최대 값 f (n) = log2n 을 가 져 옵 니 다.
          T(n)=O(log2n )
O(n^3)
2.5.
    for(i=0;i    {  
       for(j=0;j       {
          for(k=0;k             x=x+2;  
       }
    }
해: i = m, j = k 일 때 내부 순환 횟수 가 k 일 때 i = m 일 때 j 는 0, 1,..., m - 1 을 취 할 수 있 기 때문에 여기 서 가장 내부 순환 은 모두 0 + 1 +... + m - 1 = (m - 1) m / 2 회 진행 되 었 기 때문에 i 는 0 에서 n 을 취하 면 순환 은 모두 0 + (1 - 1) * 1 / 2 +... + (n - 1) n / 2 = n (n + 1) (n - 1) / 6 이 므 로 시간 복잡 도 는 O (n ^ 3) 이다.
                                  
알고리즘 의 최 악의 상황 과 기대 행 위 를 구분 해 야 합 니 다. 예 를 들 어 빠 른 정렬 의 최 악의 상황 운행 시간 은 O (n ^ 2) 이지 만 기대 시간 은 O (nlogn) 입 니 다. 매번 기준 치 를 꼼꼼 히 선택 하면 제곱 상황 (즉 O (n ^ 2) 의 확률 을 거의 0 으로 줄 일 수 있 습 니 다. 실제 적 으로 정 성 스 럽 게 이 루어 진 빠 른 정렬 은 보통 (O (nlogn) 입 니 다.시간 운행.
다음은 자주 사용 하 는 기법 입 니 다.
배열 에 접근 하 는 요 소 는 상수 시간 작업 이나 O (1) 작업 입 니 다. 하나의 알고리즘 은 2 분 검색 과 같은 데이터 요 소 를 단계별 로 절반 씩 제거 할 수 있 으 면 보통 O (logn) 시간 을 가 집 니 다. n 자 를 가 진 두 문자열 을 strcmp 로 비교 하려 면 O (n) 시간 이 필요 합 니 다. 일반적인 행렬 곱 하기 알고리즘 은 O (n ^ 3) 입 니 다.모든 요 소 를 계산 하려 면 n 대 요 소 를 곱 하고 더 해 야 하기 때문에 모든 요소 의 개 수 는 n ^ 2 입 니 다.
지수 시간 알고리즘 은 일반적으로 가능 한 모든 결 과 를 구 해 야 하 는 데 서 유래 합 니 다. 예 를 들 어 n 개 요소 의 집합 은 모두 2n 개의 키 집합 이 있 기 때문에 모든 부분 집합 을 요구 하 는 알고리즘 은 O (2n) 입 니 다. 지수 알고리즘 은 일반적으로 n 의 값 이 매우 작 지 않 는 한 너무 복잡 합 니 다. 이 문제 에서 하나의 요 소 를 추가 하면 운행 시간 이 배가 되 기 때 문 입 니 다. 불행 하 게 도 많은 문제 가 있 습 니 다.(예 를 들 어 유명한 '투어 판매원 문제') 지금까지 찾 은 알고리즘 은 모두 지수 입 니 다. 만약 우리 가 정말 이런 상황 을 만난다 면 가장 좋 은 결 과 를 찾 는 알고리즘 으로 대체 해 야 합 니 다.

2.3. 


    a=0;


    b=1;                      ①


    for (i=1;i<=n;i++) ②


    {  


       s=a+b;　　　　③


       b=a;　　　　　④  


       a=s;　　　　　⑤


    }


 ：   1   ：2,        


             2   ： n,    ->n+1     


            3   ： n-1,   ->n   


            4   ：n-1,    ->n 


            5   ：n-1,    ->n                            


          T(n)=2+n+3(n-1)=4n-1=O(n).