알고리즘의 실행 시간 계산/복잡성

Question

알고리즘의 시간 복잡도 또는 이론적 실행 시간 (psuedocode가 주어짐)을 T (n)으로 줄 단위로 계산해야합니다. 나는 그것을 시도해 봤지만, 몇 가지 혼란이있다. 예를 들어, "if"문장의 시간 복잡도는 얼마입니까? 그리고 중첩 된 루프는 어떻게 처리합니까? 코드는 내 시도와 함께 주석으로 처리됩니다.

길이 [A] = N

for i = 0 to length[A] - 1 // n - 1 
     k = i + 1     // n - 2 
     for j = 1 + 2 to length[A] // (n - 1)(n - 3) 
     if A[k] > A[j]   // 1(n - 1)(n - 3) 
      k = j     // 1(n - 1)(n - 3) 
     if k != i + 1    // 1(n - 1) 
     temp = A[i + 1]   // 1(n - 1) 
     A[i + 1] = A[k]   // 1(n - 1) 
     A[k] = temp    // 1(n - 1) 

Answer 1

블렌더 옳은 결과가 O 인 (N^2) 각각 n에 의존하는 반복 횟수가 두 중첩 루프.

더 긴 설명 :

제 1,이 경우에는,별로 중요하지 않는 경우 : O 표기법은 알고리즘의 최악의 실행 시간에 보이는 때문에, 당신은 단순히의 실행 경로를 선택하는 것 전반적인 실행 시간이 더 나 빠졌다. 예제에서 두 실행 경로 (k != i+ 1은 true 또는 false)가 런타임에 더 이상 관련되어 있지 않으므로 무시해도됩니다. 세 번째 중첩 루프가 if 안에있는 n까지 실행 중이면 O (n^3)로 끝납니다.

으로 라인 개관 :

for i = 0 to length[A] - 1 // n + 1 [1] 
    k = i + 1     // n 
    for j = 1 + 2 to length[A] // (n)(n - 3 + 1) [1] 
    if A[k] > A[j]   // (n)(n - 3) 
     k = j     // (n)(n - 3)*x [2] 
    if k != i + 1    // n 
    temp = A[i + 1]   // n*y [2] 
    A[i + 1] = A[k]   // n*y 
    A[k] = temp    // n*y 

[1] for 루프 문 i 다음 값과 N + 1 회 실행한다 : 0 (참, 루프를 계속) 1을 () 루프를 계속 ... length[A] - 1 (진정한) length[A] (거짓을 루프를 계속, 휴식 루프), 진정한

[2] 데이터를 모른 채, 당신은 if의 조건이 참 얼마나 자주 생각해야 . 이 추측은 변수를 도입하여 수학적으로 수행 할 수 있습니다. < = x < = 1 이것은 이전에 말한 내용과 같습니다 : x은 n과 독립적이므로 전반적인 런타임 복잡성에 영향을줍니다. 실행 경로를 살펴보십시오.