C/C++の宿題を片付けます 100

C/C++の宿題を片付け� ..

43:デフォルトの名無しさん
07/11/23 13:12:19
>>23
メモリの制約が、かなり厳しいね。

二分木を格納するために O(n) が必要だから
「定数個以上のメモリ」という制限は、普通は達成不能。

木以外の空間が O(1) と解釈しても普通は無理で、
再帰を使うと再帰の深さが木の深さと同じくらいになるから
スタック上に O(木の深さ) くらいの空間が必要になる。

俺は、この二分木の表現では O(1) の空間は不可能だと思う。

次ページ

続きを表示

1を表示