プログラミングの為の数学と算数 vol.2

プログラミングの為の数学と算数 vol.2 at TECH

555:デフォルトの名無しさん
06/07/20 08:09:59
拙いPerlですが。
URLﾘﾝｸ(sourcepost.sytes.net)

(i) 区間対の個数はO(nn)、重なりの有無の判定はO(1)だから、全体でO(nn)。

(ii) >>554に同じ。

(iii) 与えられた区間の始点と終点を列挙し、ソートし、各点に何個の始点・終点が重なっているか調べる。
区間のネストの数を把握しながらこの列を走査して重なりの総数を得る。
実際のコードでは始点・終点の個数の計算と最後の操作を一つのループで行っている。

次ページ

続きを表示

1を表示