关于算法的描述 所谓一个问题是指一个有待回答、通常含有几个取值还未确定的自由变量的一个一般性提问。 它由两部分构成： 一是对其关于参数的一般性描述； 二是对该问题的答案所应满足的某些特性的说明。 而一个问题的某个实例则可通过指定问题中所有参数的具体取值来得到。以下用 ΠΠ 表示某个问题，用 ΙΙ 表示其实例。 所谓一个问题实例的大小是指 为描述或表示它而需要的信息量。 所谓算法是指用来求解某一问题的、带有一般性的一步一步的过程。它是用来描述可在许多计算机上实现任一计算流程的抽象形式，其一般性可以超越任何

找最大最小元素 问题：在元素表单独或同时找出第 kk 小元素 答：利用类似于快速排序的方式来求解： 随机选择一个 pivot 比它小的数放到左边 比它大的数放到右边 这样就知道了第 kk 小的数在那个组里 然后回到 1. 递归 复杂度分析 一般情况下，每次数组数量减半，那么： 第 1 趟的时间复杂度为 O(n)O(n) 第 2 趟的时间复杂度为 O(n/2)O(n/2) … 于是： T(n) = n + {n \over 2} + {n \over 4} + \cdots = 2n = O(n)

分数背包问题 贪心选择性质的证明 设 II 为背包问题，其中设： nn 为其中物品的数量 v_iv_i 为第 ii 个物品的价值 w_iw_i 为第 ii 个物品的重量 物品以 v_i/w_iv_i/w_i 递增排序 W > w_nW > w_n 为背包的容量 设 S = (s_1, s_2, \cdots, s_n)S = (s_1, s_2, \cdots, s_n) 为一个解，贪心算法假设 s_n = \min(w_n, W)s_n = \min(w_n, W)，然后继续求解子问题 I' = (