※ 引述《Franckie ( )》之铭言： : l大的算法有问题 : input: weight{10,20,30} capacity{11,100,10} : l大跑出来的是2, : 但正确的是3 : ※ 引述《Franckie ( )》之铭言： : : 请问l大 2.b 这个步骤您要怎样实做呢? : : 这个步骤的复杂度应该不太可能是O(1)吧? 我想的是: 1.箱子的capacity必须大於自己"以上"(含自己)的总重量 所以在我们的想法里面的capacity是包含自己重量的capacity 。当然这里提供一个想法让这样 的input可以使用l大的演算法，因为我们想的是包含自己重量的 capacity，所以你只要在initialization的时候: for i<-1 to n c[i]<-c[i]+w[i] 一样可以使用l大的演算法，此步骤其T(n)=O(n)<nlgn不影响整 体的复杂度 以此题为例 原来c={11,100,10},w={10,20,30} 经过调整c={11+10,100+20,10+30} ={21,120,40} 经过sort: c={21,40,120},w={10,30,20} initialization: s[1]={box 1} i=2 s[2]=s[1]+box[2],m[2]=m[1]+1=2 因为c[2]=40>=30+10=w[1]+w[2] i=3 s[3]=s[2]+box[3],m[3]=m[2]+1=3 //偷懒 正解，不但求出的长度和正解一样，结构也相同 2.我getmaxindex()(也就是l大的2b)的时间如果我在每次insertㄧ个 box进入我的解结构的时候，就调整我的max heap是每次花费O(lgn) (因为只要把该box插入last node位置，并且不断向parent box 进行挑战和swap,T(n)=O(tree height)=O(lgn) 当我使用getmaxindex()的时候就是delete max操作，调整max heap 一样也是O(lgn)(将last node放在root，两个child box取大者和parent box 比较，挑战成功则swap，一直往下直到leaf或者挑战失败,一样O(lgn)) 调整好以後，再把box[i] insert入heap还是O(lgn), ，而他又在for i<-2 to n的回圈内，所以最多 整个回圈O(nlgn)一样不影响整体复杂度，因为Sort=O(nlgn) 整个演算法T(n)=O(nlgn) 这里会让人搞混的点是说heap sort的时间复杂度本身就是O(nlgn)没错 ，但是若是在每次insert,delete进行操作其实都"每次"都只需要O(lgn) 而非想像中的在for回圈中又*O(nlgn) --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 203.222.23.95 ※ 编辑: keeperkai 来自: 203.222.23.95 (04/23 16:08)