Matsushita's Blog

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

結果

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

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

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

Javaのメモリーサイズ

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

Runtime (Java Platform SE 6)

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

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

空間計算量

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

107の場合、10MBとなる。

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

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

時間計算量

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

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

  • O(109) : 1703ms → 2秒弱
  • O(108) : 127ms → 0.1秒 (10^-1秒)
  • O(107) : 13ms → 0.01秒 (10^-2秒)
  • O(106) : 6ms → (10^-3秒)

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