第一讲：计算复杂性理论

第一讲：计算复杂性理论

(ComplexityTheory)

计算量的概念计算量的表示算法与计算量计算复杂性影响计算复杂性的因素

优化问题及其计算的复杂性

例：组合优化问题：組合数虽然有限，但因其数量太多，寻找最优解很难。背包问题（knapsackproblem）：n个物品,2n实行可能解。旅行商问题（travelingsalespersonproblem）：都市n个,(n‐1)!实行可能解。

用有限時間可以求解，但计算时间太长，成本太高9012334567１2345优化技术与方法計算量(1)＋,－,×,÷比較：≠，≤，≥，＜，＞5种基本演算都是用1step

可以实现.実際上,×比＋多占用時間.「四舍五入」不算基本演算.

計算量(2)｛a1,a2,...,an｝：n個整数Q1.

求和（1）：

a1+a2+･･･+an.

n-1steps→O(n)算法.Q2.

求和（2）：

(1)2×a1+･･･+2×an,2n-1steps→O(n)算法.(2)2×(a1+･･･+an)

,nsteps→O(n)算法.Q3.

計算：a1b1+･･･+anbn.2n-1steps.Q4.2个ｎ×ｎ阶矩阵相乘.

n2(2n-1)steps（n2(n+n-1)）.計算量(3)計算量(4)Q5.｛a1,a2,...,an｝：n個整数

求其和为最大的部分集合.

所有的部分集合的和进行比較2n(n-1)+(2n-1)→O(n2n)算法.计算量的膨胀(1)10行×10列棋盘上米粒的数量（第1格内放1粒米，以后每格顺次增加1倍……)格序号米粒数重量(kg)112.0×10-592565.1×10-3181310722.6×10027671088641.3×10336343597383686.9×10545175921860444163.5×1085490071992547409921.8×10116346116860184273879049.2×10137223611832414348226068484.7×10168112089258196146291747061762.4×10202.4×108亿吨计算量的膨胀(2)100MIPS(megainstructionspersecond)1秒間100万回的計算＝1step用10-6秒光速3.0×1010cm/秒(10-6秒

行进300m)n101001,00010,000n10-5秒10-4秒10-3秒0.01秒n210-4秒0.01秒1秒100秒n30.001秒

1秒16.6分277時間2n0.001秒1014世紀10284世紀n!0.036秒10141世紀102551世紀宇龄：

宇宙的年齢1.5×108世紀（１５０億年）计算机速度增加的效果（1）10秒間的計算量？100MIPS10倍100倍1000倍

n1071081091010n23千1万

3万

10万n3215462

1千

2千2n2327

30

33

n!101112131000倍⇒1step用10-9秒⇒

10-9秒光可以行进30cm计算机速度增加的效果（2）计算速度1秒可以求解问题的规模

O(2n)O(n)O(n2)O(n5)O(n10)100100100100100101200141115107103100031615812610710000100025115811010000031623982001131000000100006312511000001171000000031623100031610000001201000000001000001585398平行（并列）計算的场合0.5cm见方小碎片，覆盖地球表面需要2.0×1019個.与100MIPS的单个計算機相比，能加速多少？n1001,000.2n1014世紀→0.85秒10284世紀→10263世紀n!10141世紀→10120世紀102551世紀→102530世紀问题与算法每个問題都可能有多个算法存在．每个算法的计算量（速度）都不同。例：赝品金币問題：问题：9個外观完全一样的金币.，有一个是假的（重量轻）．提问：用天秤来鉴别真伪，天秤需要使用几次？贋品金币問題算法使用2次天秤,就可以鉴别出假币.789１23456左边軽右边軽平衡１23中有偽币789中有偽币456中有偽币左边軽１32右边軽平衡１32456789计算量的表示法:上界值表示法O記号：(BigONotation)定義:O(f(n))读作orderf(n),或阶f(n)即：g(n)=O(f(n))表示对于任意定数c和m，以及对所有n＞m，有下式成立：g(n)＜cf(n)计算量的表示法——例n２+1000n→O(n２)logn+n3+1000n2→O(n3)判断：n!→O(nn)？10n2→

O(n3)？logn→

O(n)？思考：O()?优化问题的规模表示优化問題大小的参数例如：旅行商问题：都市的个数;背包问题：物品的个数注：参数的个数并不仅限于1个InputSize多项式时间算法与指数时间算法指数時間算法=用问题规模的指数函数来表示計算時間的算法非有效算法的代名詞多項式時間算法=能用问题规模的多项式函数来表示計算時間的算法高效率算法的代名詞多项式时间算法的计算时间问题规模計算時間1020304050100100010000100MIPS(millioninstructionspersecond)计算机的情形指数时间算法的计算时间100MIPS(millioninstructionspersecond)计算机的情形问题规模計算時間10203040501001宙齢=150億年旅行商问题的计算量（1）n個都市訪問的可能的巡回路线：n!的Stirling近似公式BigOh記法関数的定数倍的大小可以忽略≈旅行商问题的计算量（2）根据Stirling公式以及O（）表示法O（nn）排序问题的计算量（1）：排序問題：S=｛a1,a2,...,an｝，n個整数列，按数值大小排列dataS输入

需O(n)時間；可能的排列種類数n!种；算法中每一个比較,都增加2倍的情形数2分树的高度（比较的次数）,

log2(n!)=O(nlog

n)x＞y?yesnon!种可能的排列排序问题计算量（2）总计算时间的复杂性：O(nlog

n)dataS输入時間(或赋值时间)：O(n)

比较时间：O(nlog

n)上位取整计算量的确定例：背包问题的贪婪算法（greedyalgorithm）的计算量确定计算的复杂度时间复杂度：

计算量:计算各基本操作的实行回数（timecomplexity）空间复杂度各计算时点内存中保持数据个数的最大值（spacecomplexity）两者的总称：计算的复杂度计算复杂度的影响因素简化模型例：RTr1/2计算复杂度的影响因素简化模型：模型1.Lm计算复杂度的影响因素简化模型：模型2计算复杂度的影响因素简化模型：模型3。计算复杂度的影响因素建模假设例：高空抛球的运动轨迹。----抛物线模型假设1.没有空气阻力；假设2.地面是平面。----椭圆模型计算复杂度的影响因素探索空间1---解的近似度、满意度例：0—10之间的整数解：1-9共9个可行解（一维）0—10之间的实数解：精确到小数点后6位共有107个可行解（一维）；107n个可行解（n维）探索空间2---解空间大小例：桌子上有6根火柴，要求构建出4个三角形。计算复杂度的影响因素探索策略的选取计算复杂度的影响因素问题本身P问题NP问题（NP-hard