オーダー計算量と実際の処理時間と使用容量を比較する

結果

僕の環境では以下の値となった。言語はJava。

• 空間計算量O(N)とすると実際の使用容量はN byte程度
• 時間計算量O(10^x) とすると、10^-1*(9-x) 秒程度

※オーダーの値が小さいと誤差は出る

Javaのメモリーサイズ

Javaのメモリーサイズはメソッドによって取得することができる。

Runtime (Java Platform SE 6)

• totalMemory() : Java 仮想マシンのメモリーの総容量を返す。
• maxMemory() : Java 仮想マシンが使用を試みる最大メモリー容量を返す。

maxMemoryとは、使用メモリーがtotalMemoryに近づいた時に、更にメモリーの使用を試みる値となる。

maxMemoryは大体2GBであることが分る。

空間計算量

Int型の整数１つのバイト数は１バイトとなる。つまりO(10⁶)だと10⁶バイトとなり、1MBとなる。 10⁹個の場合は、1GBとなり、out of memory errorが発生する。

10⁷の場合、10MBとなる。

実際に図ってみても使用メモリーは40MBと妥当な値を出している。

まとめると、空間計算量O(N)とすると実際の使用容量はN byte程になった。

時間計算量

処理時間はSystem.nanoTime()によってナノセカンドを得る事ができる。

O(10⁷)だと13msで10^-2秒程となる。

• O(10⁹) : 1703ms → ２秒弱
• O(10⁸) : 127ms → 0.1秒 (10^-1秒)
• O(10⁷) : 13ms → 0.01秒 (10^-2秒)
• O(10⁶) : 6ms → (10^-3秒)

まとめると 時間計算量O(10^x) の場合、10^-1*(9-x) 秒かかる。