复杂度和测试数据 吴章昊
复杂度简介 𝑛 问题规模，一般为数据的输入量 𝑓(𝑛) 算法中基本操作重复执行的次数—频度 是问题规模n的某个函数 算法的时间复杂度 算法中各语句的频度之和𝑇(𝑛) 𝑇 𝑛 =𝑂 𝑓 𝑛 随问题规模的增大，算法执行时间的增长率和𝑓(𝑛)的增长率相同
大O表示法 O的含义 存在正的常数𝑐和𝑛0，使得当𝑛 𝑛0时， 0 𝑇(𝑛) 𝑐∗ 𝑓(𝑛) 无穷大渐近 E.g. 4 𝑛 2 +2𝑛+𝑛𝑙𝑜𝑔𝑛=𝑂 𝑛 2 𝑛𝑙𝑜𝑔𝑛+100𝑛=𝑂(𝑛𝑙𝑜𝑔𝑛)
* 一些符号 𝑓 𝑛 =𝑂 𝑔 𝑛 渐近上限 𝑓 n =o g n 渐近可忽略不计 lim 𝑓 𝑛 𝑔 𝑛 =0 𝑓 𝑛 =𝑂 𝑔 𝑛 渐近上限 𝑓 n =o g n 渐近可忽略不计 lim 𝑓 𝑛 𝑔 𝑛 =0 𝑓 𝑛 =Ω 𝑔 𝑛 渐近下限 当且仅当g n =O f n 𝑓 𝑛 =Θ 𝑔 𝑛 渐近紧约束(当且仅当𝑓 𝑛 =𝑂 𝑔 𝑛 且𝑓 𝑛 =Ω 𝑔 𝑛 )
一些栗子 𝑂(1) 例一： x++; s = 0; 例二： 𝑂( 𝑛 3 ) for (i =0; i < n; ++i) { for (j = 0; j < n; ++j) { c[i][j] = 0; for (k = 0; k <n; ++k) c[i][j] += a[i][k] * b[k][j]; } 𝑂( 𝑛 3 )
还有些栗子 例三： i=n-1; while ( i>=0 && A[i]!=K ) return i; i=i-1; return i; 最好 𝑇(𝑛)=𝑂(1) 最坏 𝑇(𝑛)=𝑂(𝑛) 平均时间复杂度：所有可能的输入实例以等概率出现的情况 𝑇(𝑛)=(1+2+…+𝑛)/𝑛 算法的时间复杂度：𝑂(𝑛) 由于平均复杂度常常比较难以计算，有时会以最坏复杂度为准
最后一个栗子 例四： void foo(int l, int r) { if (l >= r) return; for (int i = l; i <= r; ++i) { cout << “I am stupid!” << ‘\n’; } int mid = (l + r) / 2; foo(l, mid); foo(mid + 1, r);
最后一个栗子 𝑇 𝑛 = 2𝑇 𝑛 2 +Θ 𝑛 根据主定理 𝑇 𝑛 =𝑂(𝑛𝑙𝑜𝑔𝑛) 常见算法及复杂度 算法 递推关系式 运算时间 𝑇 𝑛 = 2𝑇 𝑛 2 +Θ 𝑛 根据主定理 𝑇 𝑛 =𝑂(𝑛𝑙𝑜𝑔𝑛) 常见算法及复杂度 算法 递推关系式 运算时间 折半搜索 𝑇 𝑛 =𝑇 𝑛 2 +Θ(1) Θ log 𝑛 二分治 𝑇 𝑛 =2𝑇 𝑛 2 +Θ n Θ(𝑛𝑙𝑜𝑔𝑛)
目前的OJ 目前限时1秒的OJ 大部分，把n带入前面的大O表示法得到的结果： O(n^4): n = 50, n = 100 O(n^3) : n = 100, n = 300 O(n^2): n = 1000, n = 5000 O(nlogn): n = 300000 以上仅供参考
空间复杂度没啥好讲的 一个a[n][m]的数组复杂度就是O(nm) 一个变量t = 100000复杂度就是O(1)
测试数据的选取 边界条件 多试试小数据 对拍大法好 经验 + 感觉
对拍大法 test.bat :Loop rand.exe > rand.in origin.exe < rand.in > originans.out ans.exe < rand.in > stdans.out fc originans.out stdans.out if not errorlevel 1 goto Loop pause
谢谢~