搜索
作业作业一做得较好1.做得较好.2(1)递归树()...)43(43)(2cncncnnT+++=)(...])43(431[442nOcn=+++=(2)Master定理44)()(5log2nΘnT=1)()(3主元素测试（可排序）3.主元素测试（可排序）算法1:算法1:对A排序；顺序检索A，计数每个元素x的个数.保留数目最多的元素及其个数j检索完成后如果留数目最多的元素x及其个数j.检索完成后如果jn/2，x就是主元素,否则A中没有主元素.T(n)=O(nlogn)+O(n)=O(nlogn)算法2:找出A的中位数x顺序比较计数x在A中出算法2:找出A的中位数x,顺序比较计数x在A中出现的次数j.如果jn/2，则x就是主元素，否则不存在主元素在主元素.T(n)=O(n)+O(n)=O(n)命题如果是主元素则是中位数2命题：如果x是主元素，则x是中位数.主元素测试（不可排序）算法3芯片测试算法主元素测试（不可排序）算法3：芯片测试算法淘汰过程：将元素两两分组进行比较，如果相等则选一个进入下一轮，否则两个都淘汰.轮空元素需特殊处理.命题：如果存在主元素，测试后一定会留下来性质1每轮测试后输入至少减半测试至多l次1.每轮测试后输入至少减半，测试至多logn次2.中间被淘汰的不是主元素.如果最后有2个元素留下来，测试该元素在数组中的个数即可做出判断试该元素在数组中的个数，即可做出判断时间3时间：O(n)主元素测试（不可排序）主元素测试（不可排序）算法4：栈处理设计思想：设立栈S，大小为n/2依次检查A中元素x：如果设计思想：设立栈S，大小为n/2.依次检查A中元素x：如果栈为空或者x=栈顶元素，x进栈；否则弹出栈顶元素.全部检查完成后，若栈为空，回答“No”；如果有元素，则计数检查完成后，若栈为空，回答；如果有元素，则计数该元素在A中出现的次数，当次数n/2时回答“yes”否则“No”命题：1．如果x为主元素，则x一定保留在栈里2．栈中只有1种元素4时间：O(n)4求X与Y的中位数4.求X与Y的中位数的中位数和的中位数比较如果则问题X的中位数x和Y的中位数y比较，如果xy，则问题归约为X[n/2..n]，Y[0..n/2]子问题，否则归约为X[0..n/2]与Y[n/2..n]子问题，每次比较后子问题减半T(n)=T(n/2)+1，T(n)=O(logn)55求最接近中位数的k个数5.求最接近中位数的k个数算法算法：1.找S的中位数x2S的每个数与相减求绝对值2.S的每个数与x相减，求绝对值//每个数的下标与其绝对值建立对应关系3在n个绝对值中找第k小y3.在n个绝对值中找第k小y4.依次检查每个绝对值，如果它小于y，那么对应的数是与x最近的k个数之一.如果小于y的不足k个，用等数是与x最近的k个数之.如果小于y的不足k个，用等于y的数补足.时间T(n)=O(n)66计算逆序6.计算逆序算法:算法:1.初始逆序数N＝02将数组从中间划分成前后两个子数组L和L2.将数组从中间划分成前后两个子数组L1和L23.递归处理L14递归处理L4.递归处理L25.在归并L1与L2时计数L1与L2的元素产生的逆序数m（当L1的首元素大于L的首元素时L的m个元素都与L的首元的首元素大于L2的首元素时，L1的m个元素都与L2的首元素构成逆序）,将m加到N上.时间复杂度函数：⎧+=1)2/(2)(nnTnT时间复杂度函数：T()l+1⎩⎨⎧=−+=0)1(1)2/(2)(TnnTnT7T(n)=nlogn–n+1