1 第六章 离散优化模型 在某些优化问题中，变量（或部分变量）只能取自于一个离散的集合，这个离散集合有时是可列无限集（如整数全体等），有时甚至是有限集，此时我们遇到的就是一个离散优化问题。 § 6 .1 算法计算量的比较 有人认为，只要计算机好，不怕做不出题目，这种想法对吗？抱有这种想法的人实际上犯了一个常识性的错误，殊不知计算机好只不过是硬件好，要能充分发挥出计算机的作用,还需要有好的软件来配合。没有好的算法，你有再好的计算机也没用。 例 6 .1 （整理问题） 给定 n 个实数 a1, a2,… , an，要求将它整理成由小到大排列（或由大到小排列）的顺序：b1, b2,… , bn，b1≤ b2≤… ≤ bn。 （算法 1 ） 取出 a1, a2,… , an 中的最小者，令其为 b1。从 a1, a2,…, an 中去除b1，在余下的 n—1 个数中选出最小者，令其为 b2，„，一直进行下去，直至最后得到 b1, b2,… , bn。 容易看出，为了排出 b1, b2,… , bn，算法共作了 (1)2n n 次比较。 （算法 2 ）（算法用归纳法定义） 步 0 b1←a1 步 1 设已排好 b1,„,bk (1≤k
