Home Knuth's Optimization
Post
Cancel

Knuth's Optimization

Knuth’s Optimization


1. Introduction

  • Knuth’s Optimization은 최적 이진트리 문제(optimal binary tree problems)에 적용하는 특별한 Optimization 이다.
  • 시간복잡도(time complexity)을(를) \(O(N^3)\)에서 \(O(N^2)\)로 줄인다.
  • 다음의 Conditions 들을 만족해야 활용가능하다.

2. Conditions

  • 반복되는 구조가 다음의 케이스 일 때 활용 가능
  • \[dp[i][j] = \min_{i < k < j}{dp[i][k] + dp[k][j]} + C[i][j]\]
  • 적용가능성의 충분 조건은
  • \[A[i][j - 1] \le A[i][j] \le A[i + 1][j]\]
  • Where,
    • \(A[i][j]\)은(는) 최적의 답을 주는 가장 작은 k
    • \[dp[i][j] = dp[i - 1][k] + C[k][j]\]
    • \(C[i][j]\)는 주어진 cost function
  • 가장 중요한 것은 Knuth’s Optimization은 \(C[i][j]\)이 다음의 두 조건을 만족해야 활용 가능
    • Quadrangle inequality (사각 부등식)
      • \[C[a][c] + C[b][d] \le C[a][d] + C[b][c], a \le b \le c \le d\]
    • Monotonicity (단조성)
      • \[C[b][c] \le C[a][d], a \le b \le c \le d\]

3. Example Code

4. References

This post is licensed under CC BY 4.0 by the author.

-

What is a Node.js