级数 算数级数,与末项平方同阶 t(n) = 1+2+...+n = n(n+1)2 = o(n2) 幂方级数,比幂次高一阶 t2(n) = 12+22+...+n2 = n(n+1)(2n+1)6 = o(n3) t3(n) = 13+23+...+n3 = n2(n+1)24 = o(n4) t4(n) = 14+24+...+n4 = n(n+1)(2n+1)(3n2+3n-1)30 = o(n5) 幂方级数 几何级数,与末项同阶 ta(n) = a0+a1+...+an = (an+1-1)(a-1) = o(an) 1+2+4+...+2n = 2n+1-1 = o(2n+1) = o(2n) 收敛级数 1(1×2)+1(2×3)+1(3×4)+...+1((n-1)×n) = 1-1n = o(1) 几何分布 (1-p)(1+2p+3p2+...+npn-1+...) = 1(1-p) = o(1), 0  p  1 调和级数 1+12+13+...+1n = θ(logn) 对数级数 log1+log2+log3+...+logn = log(n!) = θ(nlogn) 循环与级数 for (int i = 0; i  n; i) for (int j = 0; j  n; j) o(1) operation(i, j) for (int i = 0; i  n; i) for (int j = 0; j  i; j) o(1) operation(i, j) for (int i = 1; i  n; i = 1) for (int j = 0; j  i; j) o(1) operation(i, j) for (int i = 0; i = n; i) for (int j = 1; j  i; j += j) o(1) operation(i, j) 取非极端元素 问题:给定整数子集s,|s| ≥ 3,取元素a ∈ s,要求a ≠ max(s) 且 a ≠ min(s) 算法:从s中任意取3个元素,因s为集合,元素互异,确定并排除最大值与最小值,余下元素即为结果.t(n) = o(1) 冒泡排序 问题:给定n个整数,按(非降)序排列 观察:有序序列中,任意相邻元素顺序;无序序列中,总有相邻元素逆序. 扫描交换:依次比较每对相邻元素,若逆序,则交换;若整个扫描过程中未发生交换,则排序完成,否则重复该过程. void b bblesort(int arr[], int n) { for (bool sorted = false; sorted = !sorted; n--) { for (int i = 1; i  n; i) { if (arr[i - 1]  arr[i]) { swap(arr[i - 1], arr[i]); sorted = false;