在执行的
nnn个操作中，有至多⌈lgn⌉⌈lg n⌉⌈lgn⌉个操作的次序是222的幂，这些操作的次序（即代价）如下1,2,4,8,⋅⋅⋅,2⌈lgn⌉1, 2, 4, 8, · · · , 2 ⌈lg n⌉1,2,4,8,⋅⋅⋅,2⌈lgn⌉nnn个操作的总代价为T=∑k=0⌈lgn⌉2k+(n−⌈lgn⌉)×1=2⌈lgn⌉+1−1+(n−⌈lgn⌉)≤2lgn+2+n−lgn=3lgn+n\begin{aligned} T&=\sum^{⌈lg n⌉}_{k=0}2^k + (n − ⌈lg n⌉) × 1\\ &=2^{⌈lg n⌉+1} − 1 + (n − ⌈lg n⌉)\\ &≤2^{\lg n+2} + n − lg n\\ &=3 lg n + n \end{aligned}T=k=0∑⌈lgn⌉2k+(n−⌈lgn⌉)×1=2⌈lgn⌉+1−1+(n−⌈lgn⌉)≤2lgn+2+n−lgn=3lgn+n
因此每个操作的摊还代价是
O(3lgn+nn)=O(1)O ( \cfrac{3 \lg n + n }n ) = O(1)O(n3lgn+n)=O(1)的。
当操作次序是
222的幂时，为其赋444的摊还代价，否则为其赋222的摊还代价，则每一个不为222 的幂的操作均会提供111的信用以支付差额，对于一 个nnn个操作组成的操作序列，有4×⌈lgn⌉+2×(n−⌈lgn⌉)=2×⌈lgn⌉+2n≤3lgn+n≤∑k=0⌈lgn⌉2k+(n−⌈lgn⌉)×1\begin{aligned} &4×⌈\lg n⌉+2×(n−⌈\lg n⌉) \\ &=2×⌈\lg n⌉+2n\\ &≤3\lg n+n\\ &≤\sum^{⌈lg n⌉}_{k=0}2^k+(n−⌈\lg n⌉)×1 \end{aligned}4×⌈lgn⌉+2×(n−⌈lgn⌉)=2×⌈lgn⌉+2n≤3lgn+n≤k=0∑⌈lgn⌉2k+(n−⌈lgn⌉)×1
每个操作的摊还代价都是常数，因此摊还代价都为
O(1)O(1)O(1)。
定义势函数
ΦPhi(Di)={0,i=01,i=1lgi+1,i=2⌊lgi⌋⌊lgi⌋+k,i=2⌊lgi⌋+kΦPhi(D_i) =\left\{ \begin{aligned} & 0, \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ i = 0\\ &1, \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ i = 1\\ & \lg i + 1, \ \ \ \ \ \ \ \ \ \ \ \ \ \ i = 2^{⌊\lg i⌋}\\ & ⌊\lg i⌋ + k, \ \ \ \ \ \ \ \ \ \ i = 2^{⌊\lg i⌋} + k \end{aligned} \right.ΦPhi(Di)=⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧0, i=01, i=1lgi+1, i=2⌊lgi⌋⌊lgi⌋+k, i=2⌊lgi⌋+k
则对任意的
i，Φ(Di)≥0i，Φ(D_i) ≥ 0i，Φ(Di)≥0，且Φ(Di)−Φ(Di−1)={1−i,i=2⌊lgi⌋1,i=2⌊lgi⌋+kΦ(D_i) − Φ(D_{i−1}) =\left\{ \begin{aligned} & 1-i, \ \ \ \ \ \ \ \ i = 2^{⌊\lg i⌋}\\ & 1, \ \ \ \ \ \ \ \ \ \ \ \ \ \ i = 2^{⌊\lg i⌋} + k \end{aligned} \right.Φ(Di)−Φ(Di−1)={1−i, i=2⌊lgi⌋1, i=2⌊lgi⌋+k
所以：
∑i=1nc^=∑i=1n1=n\sum^n_{i=1}\hat{c}=\sum^n_{i=1}1=ni=1∑nc^=i=1∑n1=n
因此每个操作的摊还代价是
O(1)O(1)O(1)。
使用两个栈实现队列，将两个栈记为左右栈。
ENQUEUE\text{ENQUEUE}ENQUEUE：直接对左栈进行push\text{push}push将元素入队DEQUEUE\text{DEQUEUE}DEQUEUE：如果右栈非空，对右栈进行pop\text{pop}pop。如果右栈为空，做一个迭代：把左栈元素pop\text{pop}pop出来，push\text{push}push进右栈，直到左栈为空，再执行DEQUEUE\text{DEQUEUE}DEQUEUE。FIND-MIN\text{FIND-MIN}FIND-MIN：在左右栈基础上再加一个辅助栈，用于记录最小值。每次有元素入左栈时，判断辅助栈为空或辅助栈的栈顶元素比入栈元素更大，则将该元素压入辅助栈中，否则将辅助栈的栈顶元素重复压入辅助栈。左栈需要弹出元素时，辅助栈需要同步弹出栈顶元素。取最小值时，直接将栈顶元素弹出，返回值即最小值。
摊还分析：
设
CiC_iCi为第iii个操作的代价（假定每个操作的代价为111）设每次操作的势能D(i)=2*\text{D(i)=2*}D(i)=2*左栈元素个数，设左栈元素个数为kkk。ENQUEUE：Ci+D(i)-D(i-1)=1+2*(k+1-k)=3\text{ENQUEUE：Ci+D(i)-D(i-1)=1+2*(k+1-k)=3}ENQUEUE：Ci+D(i)-D(i-1)=1+2*(k+1-k)=3，k+1k+1k+1表示入队后的元素，所以入队摊还时间复杂度为O(1)O(1)O(1)DEQUEUE\text{DEQUEUE}DEQUEUE：
如果右栈非空,左栈有 k k k个元素： Ci+D(i)-D(i-1)=1+2(k-k)=1 \text{Ci+D(i)-D(i-1)=1+2(k-k)=1} Ci+D(i)-D(i-1)=1+2(k-k)=1
如果右栈为空,左栈有 k k k个元素： Ci+D(i)-D(i-1)=2k+1+2(0-k)=1 \text{Ci+D(i)-D(i-1)=2k+1+2(0-k)=1} Ci+D(i)-D(i-1)=2k+1+2(0-k)=1，其中 2 k 2k 2k为左栈弹出元素数+右栈压入元素数， 1 1 1表示出队一个元素，所以出队摊还时间复杂度为 O ( 1 ) O(1) O(1)
FIND-MIN\text{FIND-MIN}
FIND-MIN： 使用聚合法分析，取最小值实际上是对单个辅助栈的操作，考虑整个栈的
nn
n个操作，一个对象压入栈后，至多弹出一次，则对该栈的
nn
n个
PUSH、POP、MULTIPOP\text{PUSH、POP、MULTIPOP}
PUSH、POP、MULTIPOP的操作序列，代价至多是
O(n)O(n)
O(n)，一个操作的平均时间为
O(n)/n=1O(n)/n=1
O(n)/n=1，所以摊还复杂度为
O(1)O(1)
O(1)。
每次迭代添加包含未覆盖元素最多的集合, 直到满足全覆盖条件，时间复杂度为多项式时间
Θ(klgn)\Theta(k\lg n)Θ(klgn)
假设全集
SSS包含nnn个元素，最优覆盖包含kkk个子集合。那么我们使用的贪心算法最多会选择klnn+1k\ln n+1klnn+1个子集。
证明：
u j u_j uj：在贪心算法第 j j j次迭代还没有被覆盖的元素个数
O P T OPT OPT：最优解
k k k个最优集合必定可覆盖住该 u j u_j uj个元素，故最优集合中至少有一个集合包含至少 u j k \cfrac{u_j}k kuj个元素
- 使用贪心算法后，我们可以递推得到 u j + 1 ≤ u j − u j k = u j ( 1 − 1 k ) ≤ u j − 1 ( 1 − 1 k ) ( 1 − 1 k ) ≤ … ≤ u 0 ( 1 − 1 k ) j + 1 = n ( 1 − 1 k ) j + 1 u_{j+1}\le u_j-\frac{u_j}k = u_j(1-\frac{1}k)\le u_{j-1}(1-\frac{1}k)(1-\frac{1}k)\le…\le u_0(1-\frac{1}k)^{j+1}=n(1-\frac{1}k)^{j+1} uj+1≤uj−kuj=uj(1−k1)≤uj−1(1−k1)(1−k1)≤…≤u0(1−k1)j+1=n(1−k1)j+1 所以 u j + 1 ≤ n ( 1 − 1 k ) j + 1 u_{j+1}\le n(1-\frac{1}k)^{j+1} uj+1≤n(1−k1)j+1
lim x → + ∞ ( 1 + x n ) n = e x \displaystyle\lim_{x \rightarrow + \infty}(1 + \frac{x}{n})^n = e^x x→+∞lim(1+nx)n=ex，即存在这样一个式子 1 − x < = e − x 1-x <= e^{-x} 1−x<=e−x对所有的 x x x都成立 所以 u j ≤ u 0 ( 1 − 1 k ) j < u 0 ( e − 1 k ) j = n e − j k ( 1 − 1 k ) j = ( ( 1 − 1 k ) k ) j k ≤ e − j k n ⋅ e − j k ≤ 1 ⇔ e − j k ≤ n − 1 ⇔ − j k ≤ − ln n ⇔ j ≥ k ln n \begin{aligned} &u_j \le u_0(1-\frac{1}k)^j < u_0(e^{-{\frac{1}k}})^j = ne^{-{\frac{j}k}}\\ &(1-\frac{1}k)^j=((1-\frac{1}k)^k)^\frac{j}k\le e^{-\frac{j}k}\\ &n·e^{-\frac{j}k}\le 1\Leftrightarrow e^{-\frac{j}k}\le n^{-1}\Leftrightarrow -\frac{j}k \le-\ln n\Leftrightarrow j\ge k\ln n \end{aligned} uj≤u0(1−k1)j<u0(e−k1)j=ne−kj(1−k1)j=((1−k1)k)kj≤e−kjn⋅e−kj≤1⇔e−kj≤n−1⇔−kj≤−lnn⇔j≥klnn 当 j = k ln n j=k\ln n j=klnn，结果等于 1 1 1，也就是说没有其他的元素剩下了，此时 ( 1 − 1 k ) k ln n ≤ e − ln n (1-\frac{1}k)^{k\ln n}\le e^{-\ln n} (1−k1)klnn≤e−lnn， O P T ≥ k ≥ O P T ⋅ ( 1 − ( 1 − 1 k ) k ) ≥ 1 − 1 e OPT\ge k\ge OPT·(1-(1-\frac{1}k)^k)\ge 1-\frac{1}e OPT≥k≥OPT⋅(1−(1−k1)k)≥1−e1，所以近似比为 1 − ( 1 − 1 k ) k ≥ 1 − 1 e 1-(1-\frac{1}k)^k\ge 1-\frac{1}e 1−(1−k1)k≥1−e1，则对于一个含有 k ln n + 1 k\ln n+1 klnn+1个子集的集合覆盖， k ln n + 1 ∈ Θ ( k ⋅ ln n ) = Θ ( k lg n ) k\ln n+1∈\Theta(k·\ln n)=\Theta(k\lg n) klnn+1∈Θ(k⋅lnn)=Θ(klgn)。
当我们选择一个集合之后，删除已经被覆盖的元素。然后我们选择每个单位成本最小的集合直到覆盖所有元素。本质上每次选择覆盖未覆盖元素最多的集合。
CCC：代表到目前为止涵盖的元素集
cost effectiveness , or α\text{cost effectiveness , or α}cost effectiveness , or α：每个新覆盖节点的平均成本
伪代码：
Greedy Method:Initial CWhile C != U:Find the set Si whose cost effectiveness is the smallestthen Set C = C∪SiLet α= wi/|Si-C|For each e∈Si-C : Set price(e)= αend WhileOutput Selected sets
我们每次选取的都是
wiSi−C\cfrac{w_i}{S_i-C}Si−Cwi最小的集合SiS_iSi，即每次新添的集合SiS_iSi的新增覆盖率相对于cost\text{cost}cost值都是最大的，从而实现局部最优。
选择的集合按照先后顺序为
S1,S2,…,SmS_1 , S _2 , … , S _mS1,S2,…,Smnin _ini 是选择SiS_iSi时，其覆盖的新元素个数。
元素被覆盖的顺序
e1,e2,…,ene_1,e_2,…,e _ne1,e2,…,en 。
设
SjS_jSj第一次覆盖新元素eke_kek 。C1,...C_1,...C1,...是最优覆盖中的部分集合，覆盖了ek,…,en，ni′e_ k , … , e _n，n _i'ek,…,en，ni′ 是其覆盖的对应元素个数。不仅仅是ek,…,ene_ k ,…,e_ nek,…,en 中的元素。
∑ i n i ′ ≥ n − k + 1 , ∑ i c o s t ( C i ) ≤ O P T \sum_i n_i'\ge n-k+1, \sum_i cost(C_i)\leq OPT ∑ini′≥n−k+1,∑icost(Ci)≤OPT，因为 C i , . . . C_ i , . . . Ci,...也可能覆盖了其他元素，是从最优覆盖中选择的部分集合。
C 1 , . . . . C_1 ,.... C1,....没有与 S 1 , . . . S j − 1 S_1,...S_{j-1} S1,...Sj−1重复的。假设某个 C i C_i Ci 在 S 1 , . . . S j − 1 S_1,...S_{j-1} S1,...Sj−1中，则 e k e_k ek之后的元素会被某个 S i ( i ∈ [ 1 , j − 1 ] ) S_i(i\in[1,j-1]) Si(i∈[1,j−1])覆盖，矛盾。
∑ i c o s t ( C i ) ∑ i n i ′ ≤ O P T n − k + 1 ⟹ \cfrac{\sum_i cost(C_i) }{\sum_i n_i'}≤ \cfrac{O P T}{n − k + 1}\Longrightarrow ∑ini′∑icost(Ci)≤n−k+1OPT⟹存在某个 c o s t ( C i ) n i ′ ≤ O P T n − k + 1 \cfrac{cost(C_i)}{n_i′}≤ \cfrac{O P T}{n − k + 1} ni′cost(Ci)≤n−k+1OPT。
- 由贪心算法选出的 c o s t ( S j ) n j ≤ c o s t ( C i ) n i ′ \cfrac{cost(S_j)}{n_j}≤ \cfrac{cost(C_i)}{n_i′} njcost(Sj)≤ni′cost(Ci)。
- 对于每个 k k k都存在满足 3 3 3和 4 4 4的 C i C_i Ci
- 每个点被覆盖的代价 c o s t ( e k ) ≤ c o s t o p t ( S ) n − k + 1 cost(e_k)\le \frac {cost_{opt}(S)}{n-k+1} cost(ek)≤n−k+1costopt(S)，所以在整个贪心过程中的总代价为 ∑ c o s t ( e k ) ≤ ( 1 + 1 2 + 1 3 + ⋅ ⋅ ⋅ 1 n ) ⋅ c o s t o p t = H n ⋅ c o s t o p t \sum cost(e_k)\le(1+\frac12+\frac13+···\frac1n)·cost_{opt} =H_n·cost_{opt} ∑cost(ek)≤(1+21+31+⋅⋅⋅n1)⋅costopt=Hn⋅costopt
∑ k c o s t ( e k ) ≤ ∑ k c o s t ( C i ) n i ′ ≤ ∑ k O P T n − k + 1 ∼ ln n ⋅ O P T \sum_kcost(e_k)\leq \sum_k\cfrac{cost(C_i)}{n_i′} \leq \sum_k\cfrac{O P T}{n − k + 1}∼\ln n·OPT ∑kcost(ek)≤∑kni′cost(Ci)≤∑kn−k+1OPT∼lnn⋅OPT.
所以近似比为
lnn\ln nlnn
本文转载自: https://blog.csdn.net/weixin_56462041/article/details/128020362
版权归原作者 之墨_ 所有， 如有侵权，请联系我们删除。
版权归原作者 之墨_ 所有， 如有侵权，请联系我们删除。