看板ACMCLUB
標 題Re: [問題] 數字環
發信站批踢踢兔 (Sat Jan 22 14:24:45 2005)
轉信站ptt!Group.NCTU!grouppost
※ 引述《Freak1033 (I ain't gonna be ever17)》之銘言：
: ※ 引述《pangfeng (Liu)》之銘言：
: : 一環上有n個正整數. 現將此環剪成兩段, 要求兩段上的數字合至多差一.
: : 如何進行?
: 先花 O(n) 統計所有數字的合, 接下來設定 tail 跟 head 指向第一個數字,
: 若 tail 跟 head 間數字和大於全部的一半, 則 tail 往前走一步,
: 否則 head 往前走一步, 每次更新 head 與 tail 間數字和需要常數時間,
^^^^^^^^
不知道是不是誤會你的意思了..
這裡最壞有可能是 O(n/2) ??
: 而我們可以保證 head 與 tail 都不會往前走超過 n 次,
: 這樣 amortized 分析起來, 全部的時間不會超過 O(n).
: (趕在停電前打完, 有點亂... @_@)
--
Eric Shang-Kuan (ericsk)
Intelligent Space Lab.(Embedded Computing),
Dept. of Computer Science & Information Engineering
National Taiwan University
--
※ 發信站: 批踢踢兔(ptt2.cc)
◆ From: 140.112.31.143