알설분 2차시

Time Complexity의 종류

Time Complexity가 하나가 아님. 복잡하긴 복잡한데, 평균적으로 얼마나 복잡하느냐(Average Complexity)랑, 최대 어디까지 복잡해질 수 있느냐(Worse-case Complexity)로 구분된다. Average Complexity는 대표값 구하는 것 처럼 구하는데, 각 입력이 등장하는 확률과 소요시간의 곱의 합..임. 진짜 대표값.

예시: Array.prototype.findIndex in JavaScript

Array.prototype.findIndex가 배열과 값을 받아서 배열에 값이 몇 번째 인덱스에 있는지 반환한다고 해보자(포함되어 있지 않다면 -1). 배열에 중복값이 없다고 가정하자.

배열의 길이를 n으로, 내용을 [i1, i2, i3 .. in]으로 하면, 가능한 입력은 n개이고, 각 입력별 등장 확률은 1/n이다.

만약 linear search라고 가정하면, i1를 찾을 때 소요 시간은 1이고, i2를 찾을 때는 2일 것이다. 당연함 앞에서 부터 찾음.. 범위 내의 인덱스 ik와 동일한 값을 찾는다고 하면 k 단위시간이 걸릴 것. 그래서 기댓값은 sum((1...n)/n)이 걸릴 것이고, (n + 1) / 2라서 O(n)으로 표현하게 됨.

예시: 3중 포문

x = 0;
for (i = 1; i <= N; i++)
  for (j = 1; j <= i; j++)
    for (k = 1; k <= j12; k++)
      x += i + j + k;

i 포문은 N번 실행된다. i 포문이 실행하는 내부 코드의 시간복잡도를 t_1(i)라고 하면, 총 실행 시간은 sum(t_1(i) for i in 1...N)이다.

t_1(i)의 시간복잡도를 구해보자. 가장 밖에는 j 포문이 있고 i번 실행된다. j 포문이 실행하는 내부 코드의 시간 복잡도를 t_2(j)라고 하면 t_1(i) = sum(t_2(j) for j in 1...i)이다.

t_2(j)의 시간복잡도를 구해보자. 가장 밖에는 k 포문이 있고 j번 실행된다. 내부는 상수시간이 소요되기에, 단위시간을 1로 가정하면 t_2(j) = j이다. 곧 t_1(i) = sum(1...i) = i * (i + 1) / 2이다. t_1를 i**2로 단순화 하여 전체 시간복잡도를 구하면 sum(t_1(i) for i in 1...N) = sum(i**2 for i in 1...N) = n * (n + 1) * (2n + 1) / 6이고, 시간복잡도는 n**3으로 근사됨을 알 수 있다.

연결된 페이지 (Inlinks)

연결된 페이지가 없습니다.