企业官网建设流程全解析

技巧

常见复杂度

• i*i<n; i++：√n
• i<n; i++：n
• i < n; i *= 2 ：logn

设置循环次数为x，求x和n的关系

乘法

放缩

列表

等比

等差：（首+末）n/2

解题步骤

1. 确定每一层循环的取值范围
2. 写出关键语句(x++)的求和表达式
3. 当分析时间复杂度

例题

例1以下 C 代码的时间复杂度是____。

int count = 0; for (int i=0; i*i<n; i++) for (int j=0; j<i; j++) count++;

正确答案：O(n)

3. 当, 时间复杂度为O(n)

例2下列程序段的时间复杂度是____。

int sum = 0; for (int i = 1; i < n; i *= 2) for (int j = 0; j < i; j++) sum++;

正确答案：O(n)

1. i = 1, 2, 4, ..., 2^k(k=logn),
3. 当, 时间复杂度为O(n)

例3求整数 n(n≥0) 阶乘的算法如下，其时间复杂度是（ ）。

int fact(int n) { if (n <= 1) return 1; return n * fact(n - 1); }

正确答案：O(n)

本算法是一个递归运算，即算法中出现了调用自身的情形。递归的边界条件是 ≤1 ，每调用一次 fact()，传入该层 fact() 的参数值减 1。采用递归式来表示时间复杂度有

则 T(n)=T(n−1)+1=T(n−2)+2=⋯=T(1)+n−1=O(n) ，故时间复杂度为 O(n) 。