07/11/23 13:12:19
>>23
メモリの制約が、かなり厳しいね。
二分木を格納するために O(n) が必要だから
「定数個以上のメモリ」という制限は、普通は達成不能。
木以外の空間が O(1) と解釈しても普通は無理で、
再帰を使うと再帰の深さが木の深さと同じくらいになるから
スタック上に O(木の深さ) くらいの空間が必要になる。
俺は、この二分木の表現では O(1) の空間は不可能だと思う。
07/11/23 13:12:19
>>23
メモリの制約が、かなり厳しいね。
二分木を格納するために O(n) が必要だから
「定数個以上のメモリ」という制限は、普通は達成不能。
木以外の空間が O(1) と解釈しても普通は無理で、
再帰を使うと再帰の深さが木の深さと同じくらいになるから
スタック上に O(木の深さ) くらいの空間が必要になる。
俺は、この二分木の表現では O(1) の空間は不可能だと思う。