示例(续) 例2:赋值语句 例3: sum 0; for (i=li i<=n; 1++) for (j=li j<ni 3++) sum++i
示例 (续) 例2: 赋值语句. 例 3: sum = 0; for (i=1; i<=n; i++) for (j=1; j<n; j++) sum++; }
增长率图示 10 100 Input size n
增长率图示
最佳,最差和平均情况 芣筒法哥衢棵榘回样如果输入数 在一个n元一维数组中顺序搜索给定的K 最佳 最差 平均情况
最佳, 最差和平均情况 • 有些算法即使问题规模相同，如果输入数 据不同，时间代价也会不一样. 在一个n元一维数组中顺序搜索给定的K 最佳: 最差: 平均情况:
分析哪种情况好? 最佳情况很少考虑 最差情况很重要 平均情况通常会考虑,但有时有难度
分析哪种情况好? 最佳情况很少考虑 最差情况很重要 平均情况通常会考虑，但有时有难度
换计算机还是算法? 给定时间内,速度加快10倍的计算机处理问 题规模的增长情况 T(n 变化 n'/n 10n 1,00010,000 10n 10 20n 5005,000n2=10n 5 n log n2501.842√10n<n3<10n737 70223n3=10n 3.16 16n2=n+3
换计算机还是算法? 给定时间内，速度加快10倍 的计算机处理问 题规模的增长情况 T(n) n n’ 变化 n’/n 10n 1,000 10,000 n’ = 10n 10 20n 500 5,000 n’ = 10n 10 5n log n 250 1,842 10 n < n’ < 10n 7.37 2n 2 70 223 n’ = 10n 3.16 2 n 13 16 n’ = n + 3 -----