>現行のリチウムイオン2次電池（LIB）の数倍～10倍超の容量を持つポストLIBの存在感が急速に高まってきた。これまで実現は遠い将来と考えられていたが、技術の開発が大きく進展し始めたことに加え、既存のLIBの安全面、技術面、価格面での限界がハッキリと見えてきたからだ。

>「空間と時間の複雑性」は、O(f(n))という関数で表せます。この場合、nが入力のサイズだとすると、この関数で求められるのは、nが無限大に向かって大きくなっていく時に必要な斬近空間、または斬近時間ということになります。f(n)の重要な複雑性クラスには、In(n)、n、n In(n)、n^e、e^nがあります。これらの関数をグラフにしてみると、nが大きくなるほど、O(In(n))は、O(n)やO(n In(n))に比べてはるかに小さくなっていくということが分かります。Sean Parentが指摘するとおり、達成可能なnに関して言えば、すべての複雑性クラスはほぼ一定、ほぼ線形、ほぼ無限にということになります。

>線形探索では、先読みを有効に活かせるが、O(n)比較が必要。

>ソートされた配列の二分探索には、O(log(n))比較のみ必要。

>van Emde Boas木探索には、O(log(n))やキャッシュが有効ではないことが多い。