5-smooth数を下からn個

2^i * 3^j * 5^k なる整数 どう書く？org
どう書く？org 7667 leque: 出題時に考えていた答。平衡木を使うので、...(2^i * 3^j * 5^k なる整数) - 投稿の詳細

nobusun
求める数の個数 n なのに 時間計算量 O(log n) というのがよく判らないんです。
素人考えだと、最低 O(n)はかかるような気がするんですけど、解説をお願いできますでしょうか

ということで素人考えながら追加で考えてみた. モデルはPRAMで. あとワードモデルじゃなくってビット単位で数える.
i回目にリストに要素を追加した後の平衡木の要素数は高々3i個. (毎回1個削除して3個以下を追加するので.) 追加, 削除で木を辿る時間がO(log i). 1回の書き込みに高々i. なので, 見た感じ時間計算量はO(n^2 log n).
5-smooth数の数は大きくなるに従って疎になるけれども, n個目のビット長は高々n. なので, 空間計算量はO(n^2).

Knuth先生も書いてましたが, 最低 O(n)はかかるというのはダメでこの場合はΩ(n)です, と釈迦に説法.