Bob需要买k张显卡,因为现在显卡都很贵,所以他货比三家,找了很多卖家,所以现在有n个显卡供他选择,n>k。而且显卡i的价格是pi,pi大于0。我们假设所有价格都不一样。而Bob想要买k张显卡,且花最少的钱。
1.设计一个算法,必须用上AVL树,用来计算最理想的选购方法的总花销,这其中选购的显卡集合G属于{1...n},G的绝对值是k。这个算法必须符合时间复杂度O(nlogk)。用自己的话描述一下算法,且写出伪码。如果最后时间复杂度是O(nlogn)则不得分。
2.对于1的算法给出一个详细的时间复杂度分析
3.请您证明,算法所计算出来的结果确实是最便宜的