STA Chapter1 part1

Sublinear Time Algorithms

これまでの常識：
問題を解くのに入力すべてを見なければ話にならないとされていた。

しかし、一部を見るだけで判断できないか？（モチベーションとしては、生体情報やネットワークグラフのようにそれ自体が巨大な量を持つ問題を解きたい）
そんなことが出来るのか？ということだが、幾つか条件を簡単にすると実際に出来ることが知られている。
近似の細かさのεだとか次数の上限dなどがパラメータとしては入っている。


時間計算量に関するエントリ（http://d.hatena.ne.jp/nsasaki/20110426/1303807572）の中で、線形時間よりも早いものを扱うのが今回の話。\sqrt{x}とかも含む。

使う資料はTel Aviv University（イスラエル）の準線形アルゴリズム時間に関する授業ノート
Ronitt Rubinfeld, Sublinear time algorithms, Fall 2009
http://www.cs.tau.ac.il/~ronitt/COURSES/F09course/index.html