限界
https://gyazo.com/b475d67d6fa44dab2ce10afc9d38b681
現行のリチウムイオン2次電池（LIB）の数倍～10倍超の容量を持つポストLIBの存在感が急速に高まってきた。これまで実現は遠い将来と考えられていたが、技術の開発が大きく進展し始めたことに加え、既存のLIBの安全面、技術面、価格面での限界がハッキリと見えてきたからだ。
現行技術に迫る3つの限界、後継技術へのシフトが必須
----
空間と時間の複雑性
「空間と時間の複雑性」は、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に関して言えば、すべての複雑性クラスはほぼ一定、ほぼ線形、ほぼ無限にということになります。 アクセス時間と容量の関係
table:アクセス時間
アクセス時間 容量
レジスタ <1ns 64b
キャッシュライン 64B
L1キャッシュ 1ns 64KB
L2キャッシュ 4ns 8MB
RAM 20ns 32GB
ディスク 10ms 10TB
LAN 20ms 1PB
インターネット 100ms 1ZB
探索
線形探索では、先読みを有効に活かせるが、O(n)比較が必要。
ソートされた配列の二分探索には、O(log(n))比較のみ必要。
van Emde Boas木探索には、O(log(n))やキャッシュが有効ではないことが多い。
table:検索時間(ns)
線形 二分 vEB
8 50 90 40
64 180 150 70
512 1200 230 100
4096 17000 320 160
出典