生成组合对象的算法之生成子集幂集是包含某集合所有子集的集合,其元素个数为2的n次方,源于每个元素在子集中存在与否的二元性,这一特性在计算机科学中具有重要应用字典序是一种按位比较的排序方式,依赖元素的既定顺序生成n位格雷码可通过递归方法实现:在n-1位序列前加0构成上半部分,倒序后加1构成下半部分,合并即得也可用公式Gi = i ^ i 1直接计算,高效实用
算法设计与分析-习题5.4两个n位十进制数的积最少有2n1位,最多有2n位,由最小值和最大值相乘推导得出分治算法可用于大整数乘法,如2101×1130=2374130对数恒等式alogb c = clogb a可通过换底公式证明nlog3比3logn更适合作为算法复杂度的闭合公式,因其更符合标准表达习惯大整数乘法中乘以10被视为位移操作,不计入乘法次数,归入线性项递推关系假设拆分位数相等,虽在n为奇数时不严格成立,但不影响最终复杂度笔算乘法需约n²次一位数加法,忽略进位影响