技巧常见复杂度i*in; i√nin; ini n; i * 2 logn设置循环次数为x求x和n的关系乘法放缩列表等比等差首末n/2解题步骤确定每一层循环的取值范围写出关键语句(x)的求和表达式当分析时间复杂度例题例1以下 C 代码的时间复杂度是____。int count 0; for (int i0; i*in; i) for (int j0; ji; j) count;正确答案O(n)当, 时间复杂度为O(n)例2下列程序段的时间复杂度是____。int sum 0; for (int i 1; i n; i * 2) for (int j 0; j i; j) sum;正确答案O(n)i 1, 2, 4, ..., 2^k(klogn),当, 时间复杂度为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)1T(n−2)2⋯T(1)n−1O(n) 故时间复杂度为 O(n) 。
技巧常见复杂度i*in; i√nin; ini n; i * 2 logn设置循环次数为x求x和n的关系乘法放缩列表等比等差首末n/2解题步骤确定每一层循环的取值范围写出关键语句(x)的求和表达式当分析时间复杂度例题例1以下 C 代码的时间复杂度是____。int count 0; for (int i0; i*in; i) for (int j0; ji; j) count;正确答案O(n)当, 时间复杂度为O(n)例2下列程序段的时间复杂度是____。int sum 0; for (int i 1; i n; i * 2) for (int j 0; j i; j) sum;正确答案O(n)i 1, 2, 4, ..., 2^k(klogn),当, 时间复杂度为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)1T(n−2)2⋯T(1)n−1O(n) 故时间复杂度为 O(n) 。
)
