algorithm

예제의 시간 복잡성

1-기본 연산 (산술, 비교, 배열 요소 액세스, 할당) : 실행 시간은 항상 일정합니다 O (1)

예 :

read(x)                               // O(1)
a = 10;                               // O(1)
a = 1.000.000.000.000.000.000         // O(1)

2-then else statement : 둘 이상의 가능한 명령문에서 최대 실행 시간 만 가져옵니다.

예:

age = read(x)                               // (1+1) = 2
if age < 17 then begin                      // 1
      status = "Not allowed!";              // 1
end else begin
      status = "Welcome! Please come in";   // 1
      visitors = visitors + 1;              // 1+1 = 2
end;

따라서 위의 의사 코드의 복잡성은 T (n) = 2 + 1 + max (1, 1 + 2) = 6입니다. 따라서 큰 오는 여전히 상수 T (n) = O (1)입니다.

3-반복 (for, while, repeat) :이 명령문의 실행 시간은 반복 횟수에 해당 반복 내의 조작 수를 곱한 것입니다.

예:

total = 0;                                  // 1
for i = 1 to n do begin                     // (1+1)*n = 2n
      total = total + i;                    // (1+1)*n = 2n
end;
writeln(total);                             // 1

따라서 복잡도는 T (n) = 1 + 4n + 1 = 4n + 2입니다. 따라서 T (n) = O (n)입니다.

4-중첩 루프 (루핑 내부 루핑) : 기본 루핑 내부에 하나 이상의 루핑이 있으므로이 명령문의 실행 시간은 O (n ^ 2) 또는 O (n ^ 3)을 사용했습니다.

예:

for i = 1 to n do begin                     // (1+1)*n  = 2n
   for j = 1 to n do begin                  // (1+1)n*n = 2n^2
       x = x + 1;                           // (1+1)n*n = 2n^2
       print(x);                            // (n*n)    = n^2
   end;
end;

일반적인 러닝 타임

알고리즘을 분석 할 때 몇 가지 일반적인 실행 시간이 있습니다.

1. O (1) – 상수 시간 상수 시간은 실행 시간이 일정 함을 의미 하며 입력 크기의 영향을받지 않습니다 .

2. O (n) – 선형 시간 알고리즘이 n 개의 입력 크기를 허용하면 n 개의 연산도 수행합니다.

3. O (log n) – 실행 시간 O (log n)이있는 로그 시간 알고리즘이 O (n)보다 약간 빠릅니다. 일반적으로 알고리즘은 문제를 동일한 크기의 하위 문제로 나눕니다. 예 : 이진 검색 알고리즘, 이진 변환 알고리즘

4. O (n log n) – Linearithmic Time이 실행 시간은 종종 문제를 하위 문제로 재귀 적으로 나누고 n 번으로 병합하는 “분할 및 정복 알고리즘”에서 찾을 수 있습니다. 예 : 병합 정렬 알고리즘

5. O (n ² ) – 2 차 시간 모양 버블 정렬 알고리즘!

6. O (n ³ ) – 입방 시간 O (n ² ) 와 동일한 원리를 갖습니다 .

7. O (2 ⁿ ) – 지수 시간 n이 1000.000이면 입력이 커질수록 T (n)은 21000.000이됩니다. Brute Force 알고리즘에는이 실행 시간이 있습니다.

8. O (n!) – 팩토리얼 타임 가장 느린 !!! 예 : 출장 판매원 문제 (TSP)

이 기사 에서 발췌 . 잘 설명해야합니다.

답변

V_k = 'That's the way,' U 'I like it, ' U
U   = 'uh huh,' 'uh huh'