DouKaku? 7667 leque: 出題時に考えていた答。平衡木を使うので、...(2^i * 3^j * 5^k なる整数)

Comment detail

出題時に考えていた答。平衡木を使うので、求める数の個数を n としたとき、時間計算量は O(log n)、空間計算量は O(n) のはず。

(define (main args)
  (let ((tm (alist->tree-map '((1 . #t)) = <)))
    (let loop ((n (string->number (cadr args)))
               (rs '()))
      (cond
       ((zero? n)
        (print (reverse rs))
        0)
       (else
        (let ((m (car (tree-map-pop-min! tm))))
          (for-each (cut tree-map-put! tm <> #t)
                    (map (cute * m <>) '(2 3 5)))
          (loop (- n 1) (cons m rs))))))))

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

DouKaku?

Comment detail

Index

Feed

Other

Link

Pathtraq