junis3's profile image

junis3

April 23, 2023 00:00

Randomized Algorithm의 시간 복잡도 분석

random

Introduction

우리가 PS에 대해 배우면서 학습하는 대부분의 알고리즘은, 확률에 의존하지 않는다. 해당 알고리즘의 로직을 올바르게 구현했을 때에는 항상 정해진 시간 복잡도로 정답을 낸다. 현대 연구되는 많은 알고리즘은 그렇지 않다. 알고리즘은 확률적으로 오답을 낼 수도 있고, 정답과 적절히 가까운 근삿값만을 계산할 수도 있다. 또는 알고리즘의 수행 시간이 확률적으로 들쑥날쑥할 수 있다. 이러한 알고리즘의 가장 간단한 예시로는 피벗을 무작위로 잡는 퀵 소트 알고리즘이 있다.

무작위 알고리즘 (Randomized algorithm) 가운데, 항상 정답을 내는 것이 보장된 알고리즘을 Las Vegas Algorithm이라 한다. 그렇지 않고, 일정 확률로 정답을 내는 것만이 보장된 알고리즘을 Monte Carlo Algorithm이라 한다. 이 글에서 우리의 관심사는 Las Vegas Algorithm에 있다. Las Vegas Algorithm에서 중요한 것은 알고리즘의 수행 시간이다. 평균 수행 시간, 최악의 경우에 수행 시간, trivial한 입력들에서의 수행 시간 등이 실제 Las Vegas Algorithm들을 평가하는 주요 요소들이 될 것이다. 이 글에서는 “임의의 데이터 분포가 주어졌을 때” 평균 수행 시간을 주안점으로 분석한다. 무작위 알고리즘의 평균 수행 시간에 대한 분석이, 실은 결정론적인 알고리즘의 최악의 경우 수행 시간에 대한 분석과 같음을 보일 것이다.

예제: Game Tree Evaluation

모든 리프가 깊이 $2k$에 있는 $d$진 “게임 트리”를 $T_{d, k}$라 부르자. “게임 트리”는 다음 두 조건을 만족하는 트리이다.

  1. 트리의 리프 정점에는 값이 하나씩 배정되어 있다.

  2. 각 내부 정점의 값은 다음과 같이 정해진다. 루트의 깊이는 0이다.

    • 깊이가 짝수인 정점의 값 : 자식 정점들의 값의 max
    • 깊이가 홀수인 정점의 값 : 자식 정점들의 값의 min

이러한 트리의 루트의 값을 평가하고 싶다. Game Tree의 루트의 값을 평가하는 알고리즘을 분석할 때에, 리프의 값을 읽는 연산의 비용만을 따지자. 다른 모든 연산들의 수행 시간은 무시하자. 결정론적인 알고리즘을 사용하면, 최악의 경우에 모든 ($d^{2k}$개) 리프 정점의 값을 읽어야 한다. 어떤 알고리즘을 사용하든, 트리를 적응적으로 구성하면 모든 정점을 읽을 때까지 루트의 값이 결정되지 않도록 할 수 있다.

$d=2$라고 하자. 결정론적인 알고리즘은 최악의 경우에 $4^k$개의 리프를 모두 읽는다. 랜덤 순서로 DFS를 수행하는 알고리즘은, 평균 $3^k$개의 리프를 읽는다. 리프의 개수가 $n$개라 할 때, 평균 수행 시간은 $n^{log_4 3 } \approx n^{0.793}$로 볼 수 있다.

$n^{log_4 3}$보다 더 빠르게 동작할 수 있는 랜덤 알고리즘이 존재하는가? 존재하지 않는다! Minimax principle을 소개하고, 이를 이용해 이 사실을 증명할 것이다 Minimax principle은, 랜덤화된 알고리즘의 평균 수행 시간에 대한 하계(lower bound)를 제시해준다.

제로섬 게임

두 친구 R과 C가, 1000원을 걸고, 이를테면 가위바위보를 한다. 각 친구에게 선택지는 (1) 바위, (2) 가위, (3) 보가 있다. 선택지의 집합은 {바위, 가위, 보}이다.

이 때, 두 사람의 payoff matrix는

\[M = \begin{bmatrix} 0 & 1000 & -1000 \\ -1000 &0 &1000 \\ 1000 & -1000 & 0 \end{bmatrix}\]

가 된다. $M_{ij}$는 친구 R이 $i$번째 선택지를 고르고, 친구 C가 $j$번째 선택지를 골랐을 때 R이 버는 돈이다.

일반적인 2인 제로섬(zero-sum) 게임에 대해 생각해 보자. R에게 $n$가지, C에게 $m$가지 선택지가 있을 때, 크기 $n \times m$의 “Payoff matrix” $M$을 생각한다. $M_{ij}$를 R이 $i$번째 선택지, C가 $j$번째 선택지를 골랐을 때 R의 이득 (C의 손해)로 정의한다. 각자 자신의 payoff를 최대화하는 선택을 하고 싶어하기에, R은 $M_{ij}$ 값이 가장 큰 $i$를 고르고 싶어하고, C는 $M_{ij}$ 값이 가장 작은 $j$를 고르고 싶어한다.

이 때, 누가 먼저 고르느냐에 따라 게임의 균형이 달라질 수 있다. R이 먼저 고를 때, C는 R이 고른 다음 고른다. C는 R이 $i$번 선택지를 골랐음을 알기 때문에 그에 맞춰서 $M_{ij}$를 최소화하는 $j$를 고를 것이다. payoff는 $\min_j M_{ij}$와 같을 것이다. R은 이와 같은 C의 전략을 알고 있으므로, C가 고른 뒤의 payoff인 $\min_j M_{ij}$를 최대화하는 $i$를 고를 것이다. 따라서, R이 먼저 선택할 때 게임의 균형 payoff는 $V_R = \max_i \min_j M_{ij}$이 될 것이다. C가 먼저 선택할 때 게임의 균형 payoff는 비슷하게 $\min_j \max_i M_{ij} = V_C$로 계산할 수 있을 것이다. 이 때,

정리 1. 다음이 항상 성립한다.

\[V_R = \max_i \min_j M_{ij} \le \min_j \max_i M_{ij} = V_C\]

증명. 상대의 선택을 모르는 채로 선택하는 것보다 상대의 선택을 아는 채로 선택하는 것이 더 낫다는 사실은 직관적이다. 이를 산술적으로 증명하면: 모든 $i, j$에 대해 $\min_j M_{ij} \le \max_i M_{ij}$임을 보이면 주어진 명제를 보일 수 있다. $\min_j M_{ij} \le M_{ij} \le \max_i M_{ij}$가 성립하므로, 증명이 끝났다.

정리 1에서 등호가 성립하면, 둘 모두에게 (고정된) 최적해가 있다. 예를 들어,

\[M = \begin{bmatrix} 0 & 1 & 2 \\ -1 & 0 & 1 \\ -2 & -1 & 0 \end{bmatrix}\]

일 때의 최적해는, R의 선택 $\rho=1$, C의 선택 $\gamma = 1$이다. 이 때의 payoff는 $V = M_{1,1} = 0$이다.

확률적 전략

지금까지는 결정론적인 전략(pure strategy)만을 생각했다. 확률적 전략(mixed strategy)을 생각해 보자. R가 각각의 선택지를 택할 확률에 대한 확률 분포를, 크기 $n$인 벡터 $\mathbf{p}$로 나타내고, C가 각각의 선택지를 택할 확률에 대한 확률 분포를, 크기 $m$인 벡터 $\mathbf{q}$로 나타내자. 물론 이 때 $\sum_{i=1}^n p_i = 1$, $\sum_{j=1}^n q_j = 1$이 성립해야 한다. 이 때의 payoff는 확률 변수이며,

\[E(\textrm{payoff}) = \mathbf{p}^T M \mathbf{q} = \sum_{i=1}^n \sum_{j=1}^m p_i M_{ij} q_j\]

이다. 이번에도 “누가 먼저 전략을 결정하는가”가 주요한 요소가 될 것이다.

  1. R이 먼저 전략 $\mathbf{p}$를 결정한다.

  2. C가 $\mathbf{p}$를 참조해서 전략 $\mathbf{q}$를 결정한다.

과 같은 전략을 쓸 때의 payoff의 기댓값을 $V_R$이라 두자. $V_C$도 비슷하게 C가 먼저 전략을 결정하고 R이 전략을 결정할 때의 payoff의 기댓값으로 정의하자. $V_R$과 $V_C$는 다음과 같이 정의된다.

\[V_R = \max_\mathbf{p} \min_\mathbf{q} \mathbf{p}^T M \mathbf{q}\] \[V_C = \min_\mathbf{q} \max_\mathbf{p} \mathbf{p}^T M \mathbf{q}\]

앞선 정리 1에서 한 발 더 나아가, 이번에는 항상 등호가 성립한다. 이를 von Neumann의 Minimax Theorem이라 부른다.

정리 2 (von Neumann’s Minimax Theorem)

행렬 $M$으로 정의되는 2인 제로섬 게임에 대해,

\[\max_\mathbf{p} \min_\mathbf{q} \mathbf{p}^T M \mathbf{q} = \min_\mathbf{q} \max_\mathbf{p} \mathbf{p}^T M \mathbf{q}\]

즉, $V_R = V_C$이다.

한 사람의 전략 (ex. $\mathbf{p}$)이 정해지고 나면, $\mathbf{p}^T M \mathbf{q}$는 반대편 사람의 전략 (ex. $\mathbf{q}$)에 대한 선형 함수가 된다. 따라서 두 번째로 선택하는 사람의 최적 전략은 (선형인 이상 하나의 선택지에 “올인”하는 게 최적이므로) 항상 결정론적인 전략이 된다. 따라서 정리 2는 다음과 같이 다시 쓸 수 있다.

정리 2

$e_k$는 $k$번째 원소만 1인 단위 벡터로 정의하자. 행렬 $M$으로 정의되는 2인 제로섬 게임에 대해,

\[\max_\mathbf{p} \min_j \mathbf{p}^T M e_j = \min_\mathbf{q} \max_i e_i^T M \mathbf{q}\]

증명

먼저 $\max_\mathbf{p} \min_j \mathbf{p}^T M e_j \le \min_\mathbf{q} \max_i e_i^T M \mathbf{q}$를 보인다. 이는 $\sum_{i=1}^m p_i = 1$, $\sum_{j=1}^n q_j = 1$를 만족하는 모든 벡터 $\mathbf{p}$, $\mathbf{q}$에 대해

\[\min_j (\mathbf{p}^T M)_j \le \max_i (M \mathbf{q})_i\]

임을 보이는 것과 같다.

\[\min_j (\mathbf{p}^T M)_j = 1 \cdot \min_j (\mathbf{p}^T M)_j \\ = \sum_i \mathbf{p}_i \min_j (\mathbf{p}^T M)_j \\ = \sum_i \left( \mathbf{p}_i \cdot \min_k (\mathbf{p}^T M)_k \right) \\ \le \sum_i \mathbf{p}_i (A \mathbf{q})_i \\ = \mathbf{p}^T A \mathbf{q}\]

이다. 같은 방법으로 $\mathbf{p}^T A \mathbf{q} \le \max_ i (M \mathbf{q})_ i$도 보일 수 있기 때문에, $\le$ 방향 부등식의 증명이 끝났다. 다음으로 $\max_\mathbf{p} \min_j \mathbf{p}^T M e_j \ge \min_\mathbf{q} \max_i e_i^T M \mathbf{q}$를 증명한다. 이는 임의의 $i$, $j$에 대해

\[\max_\mathbf{p} \mathbf{p}^T M e_j \ge \min_\mathbf{q} e_i^T M \mathbf{q}\]

를 보이는 것과 같다.

\[\max_\mathbf{p} \mathbf{p}^T M e_j \ge \max_i e_i^T M e_j \\ \ge e_i^T M e_j \\ \ge \min_j e_i^T M e_j \\ \ge \min_\mathbf{q} e_i^T M \mathbf{q}\]

이기 때문에 $\ge$ 방향 부등식의 증명도 끝났다. 이로 증명이 끝났다.

Yao’s Technique

위의 게임 이론에 대한 논의를 다음과 같이 비유해서 무작위 알고리즘에 대한 논의에 적용할 수 있다.

  • C : 문제를 푸는 알고리즘을 만드는 사람
  • R : 문제에 대한 입력을 만드는 사람

이 때 payoff를 알고리즘의 수행 시간으로 정의하면, 동일하게 $V_C$와 $V_R$을 정의할 수 있다.

  • $V_C$ : 가장 빠른 결정론적 알고리즘의 평균 수행 시간이 최대가 되도록 입력 분포 (dataset)를 결정했을 때, 가장 빠른 결정론적 알고리즘의 최악의 경우 수행 시간

  • $V_R$ : 문제에 대한 임의의 Las Vegas 알고리즘에 대해, 평균 수행 시간이 가장 큰 입력에 대한 평균 수행 시간

정리 2를 알고리즘에 비유하기 위해, 다음과 같이 용어를 정의한다.

  • $\mathcal{I}$ : 문제에서 가능한 입력의 (유한) 집합
  • $\mathcal{A}$ : 문제를 푸는 결정론적 알고리즘의 (유한) 집합
  • $C(I, A)$ ($I \in \mathcal{I}$, $A \in \mathcal{A}$) : 알고리즘 $A$에 입력 $I$를 넣었을 때의 수행 시간
  • $\mathbf{p}$: $\mathcal{I}$ 위에서의 입력의 분포, $I_\mathbf{p}$ : 분포 $\mathbf{p}$에 따라 고른 입력
  • $\mathbf{q}$: $\mathcal{A}$ 위에서의 알고리즘의 분포, $I_\mathbf{q}$ : 분포 $\mathbf{q}$에 따라 고른 알고리즘

이 때, 정리 2를 다음과 같이 서술할 수 있다.

\[\max_\mathbf{p} \min_\mathbf{q} \mathbf{E} [ C(I_\mathbf{p}, A_\mathbf{q})] = \min_\mathbf{q} \max_\mathbf{p} \mathbf{E} [ C(I_\mathbf{p}, A_\mathbf{q})]\] \[\max_\mathbf{p} \min_{A \in \mathcal{A}} \mathbf{E} [ C(I_\mathbf{p}, A)] = \min_\mathbf{q} \max_{I \in \mathcal{I}} \mathbf{E} [ C(I, A_\mathbf{q})]\]

결국은 앞서 정의한 $V_C$와 $V_R$이 같다는 결론으로 귀결된다. 아래는 위 정리의 따름정리이면서, Yao’s Minimax Principle이라고 부르는 정리이다.

정리 4 (Yao’s Minimax Principle)

$\mathcal{I}$ 위의 분포 $\mathbf{p}$, $\mathcal{A}$ 위의 분포 $\mathbf{q}$에 대해, $\min_{A \in \mathcal{A}} \mathbf{E}[C(I_\mathbf{p}, A)] \le \max_{I \in \mathcal{I}} \mathbf{E}[C(I, A_\mathbf{q})]$.

즉, 어떤 문제를 푸는 무작위 알고리즘의 worst case time complexity의 하한을 계산하기 위해서는, 결정론적 알고리즘의 시간 복잡도의 상한을 계산하는 것으로 충분하다는 것이다. 문제에 대한 입력 분포를 적절히 구성해서, 해당 입력 분포 아래에서 최적의 알고리즘의 시간 복잡도를 계산하는 문제로 바꿀 수 있다.

Application

Yao’s Minimax Principle을 이용해 앞서 다룬 Game Tree Evaluation 문제에서 $d=2$일 경우의 하계를 계산해 보자. 이 글에서는 $n^{0.694}$ 정도의 하계만을 보일 것이다. 앞서 보인 알고리즘의 수행 시간은 $n^{0.793}$이다.

일단, 문제를 간소화하자. $T_{2, k}$의 루트의 값은, 내부 정점에 모두 NOR이 적혀있는 똑같이 생긴 트리의 루트의 값과 같다. NOR 함수는, 두 입력이 모두 0이면 1을, 그렇지 않으면 0을 반환하는 함수이다. 즉, AND-OR 트리는, 사실 NOR 트리와 같다. 따라서, NOR 트리의 값을 평가하는 알고리즘의 시간 복잡도의 하계를 계산할 것이다.

가장 빠른 알고리즘이 평균적으로 가장 많은 개수의 리프를 방문하도록 입력 분포를 구성할 것이다. 더 좋은 입력 분포를 제시할수록 더욱 tight한 bound를 보일 수 있다.

각 리프가 $p = (3 - \sqrt{5}) / 2$의 확률로 1인 트리를 생각하자. 두 자식 정점이 각각 $p$의 확률로 1이면, 부모 정점 또한 $p$의 확률로 1임을 보일 수 있다. 따라서, 이 트리에서 모든 정점은 $p$의 확률로 1이다. 여기서 점화식을 잘 쓰면, 평균 $2-p$개의 리프를 보게 됨을 알 수 있고, $n^{log_2(2-p)} \approx n^{0.694}$의 시간이 들게 할 수 있다.

다른 몇 개의 문제들에 대해서도 Yao’s Minimax Principle을 사용하여 randomized algorithm의 하한을 계산해볼 것이다. 아래에 서술하는 하한보다 더욱 tight한 하한이 존재할 수 있다.

문제 1: 차수 0인 정점 찾기

정점이 $n$개인 그래프가 있다. 이 그래프에 차수(degree)가 0인 정점이 존재하는지 판별하고 싶다. 다음과 같은 질문을 할 수 있다.

  • 그래프의 정점 $u$, $v$에 대해, 그래프에서 두 정점을 잇는 간선이 존재합니까?

질문의 개수를 최소화하여 차수가 0인 정점이 존재하는지, 만약 존재한다면 어떤 정점인지 알아내어야 한다.

이 문제에서는 가능한 문제의 집합과 가능한 알고리즘의 집합이 유한하므로, Yao’s Minimax Principle을 이용할 수 있다. Randomized algorithm의 하한을 생각하는 대신, 최적의 deterministic algorithm이 가장 많은 질문을 하도록 하는 입력 분포를 생각한다. 가장 많은 질문을 하도록 하는 입력은 물론 perfect matching 자체일 것이다. 정점이 $n$개인 그래프의 부분 집합인 다음 집합 $S$으로부터 균등하게 무작위로 고른 입력을 생각하자.

\[S = \left\{ G : v \in V(G) \Rightarrow \mathrm{deg}(v) = 1\right\}\]

이 분포로 뽑은 그래프 $G$의 perfect matching을 알기 위해 필요한 질문의 수를 $T(n)$이라 하자. $G$의 1번째 정점에 대해 연결될 수 있는 서로 다른 정점의 후보는 $n-1$개 있다. 각 정점 후보는 동일한 확률을 지니므로, 1번째 정점과 연결된 정점을 알기 위해서는 1번째 정점에 평균 $(n-1)/2$번의 질문을 해야 한다. 1번째 정점의 상대 정점을 알게 된 이후에는 1번째 정점과 상대 정점에 한 질문이 모두 무의미해지므로, $T(n) \ge (n-1)/2 + T(n-2)$가 성립한다.

따라서, $T(n) \ge n^2/8$이다. 즉 이 문제를 해결하는 어떠한 무작위 알고리즘도 최악의 데이터에 대해 평균 $n^2/8$번 이상의 질문을 해야 한다.

문제 2: 연속된 기록 찾기

$n$번에 걸쳐 나타난 신호의 기록이 있다. 각각의 신호는 1 또는 0을 가지는 불리언 값이다. 신호를 수열 $a_1, \cdots, a_n$으로 나타내자. 여기서, “세 번 연속해서 1이 나온 기록이 존재하는지” 판별하고 싶다. 이 문제에서는 “어떤 신호의 값을 읽는 작업”의 수를 수행 시간의 지표로 삼는다. 즉, 문제 1에서 질문의 횟수를 최소화했던 것과 같이, 문제 2에서는 신호의 값을 읽는 횟수를 최소로 하여 문제를 해결해야 하는 것이다.

마찬가지로, Yao’s minimax principle을 이용해 결정론적인 알고리즘이 최대한 많은 질문을 하도록 하는 분포를 생각한다. 다음 집합 $S$에서 균등하게 무작위로 고른 입력을 생각하자.

$S :=$ 다음 조건을 만족하는 수열

  1. substring으로 111이 나타나지 않음
  2. 11로 시작하거나 11로 끝나지 않음
  3. 0이 연속해서 2번 이상 나타나지 않음

이 분포로 뽑은 수열 $arr$에 111이 나타나지 않음을 보이려면, 수열에 있는 모든 0 (양끝에 있는 0을 제외하고)에 대해서 질문해야 한다. 모든 0의 바로 왼쪽과 바로 오른쪽에 1이 있기 때문이다. 따라서, 알고리즘은 일단 모든 0의 위치를 찾아아 한다. 이 때 필요한 질문의 수의 기댓값을 $T(n)$이라 하자.

어떤 인덱스 $x$에 대해서도 $arr[x] = 0$일 확률은 1/2 이하이기 때문에, $arr[x] = 0$인 어떤 인덱스 $x$를 찾기 위해 필요한 질문의 수의 기댓값은 2 이상이다.

알고리즘을 실행하는 중, 수열에서 $arr[x] = 0$을 찾았다고 하자. 이 때, 전체 수열에서 $x-1$, $x$, $x+1$번째 원소를 제외해서 만든 양쪽 부분수열 $arr[0..x-1)$와 $arr[x+2..n)$는 $S$의 원소이며, 두 부분수열의 결과는 앞선 결과와 독립이다. 따라서, $T(n) \ge 2 + T(x-1) + T(n-x-2)$이며, 귀납적으로 $T(n) \ge 2/3 n$이다.