Java基础(三) 时间复杂度
时间复杂度
T(n)：
n次访问的执行总次数为T(n)
T(n)=O(f(n))
f(n)： 时间复杂度。
O：
T（n）经过简化算法得到的时间复杂度f(n)。
最坏情况下的。
所以我们一般写时间复杂度O(f(n))，如
T（n）=O（n）
1，例子
1，对于顺序执行
时间复杂度等于最大的时间复杂度分区/最大路径。
1 void aFunc(int n) {
2 // 第一部分时间复杂度为 O(n^2)
3 for(int i = 0; i < n; i++) {
4 for(int j = 0; j < n; j++) {
5 printf("Hello, World!
");
6 }
7 }
8 // 第二部分时间复杂度为 O(n)
9 for(int j = 0; j < n; j++) {
10 printf("Hello, World!
");
11 }
12 }此时的时间复杂度等于0(n^2)。
2，条件判断
同上文
1 void aFunc(int n) {
2 if (n >= 0) {
3 // 第一条路径时间复杂度为 O(n^2)
4 for(int i = 0; i < n; i++) {
5 for(int j = 0; j < n; j++) {
6 printf("输入数据大于等于零
");
7 }
8 }
9 } else {
10 // 第二条路径时间复杂度为 O(n)
11 for(int j = 0; j < n; j++) {
12 printf("输入数据小于零
");
13 }
14 }
15}此时的时间复杂度等于0(n^2)。
2，一些题
1，基础
1void aFunc(int n) {
2 for (int i = 0; i < n; i++) {
3 for (int j = i; j < n; j++) {
4 printf("Hello World
");
5 }
6 }
7}解答：
1，当 i = 0 时，内循环执行 n 次运算，当 i = 1 时，内循环执行 n - 1 次运算……当 i = n - 1 时，内循环执行 1 次运算。 2，所以，执行次数 T(n) = n + (n - 1) + (n - 2)……+ 1 = n(n + 1) / 2 = n^2 / 2 + n / 2。 3，根据 大O推导法 可以知道，此时时间复杂度为 O(n^2)。
2，log进阶
void aFunc(int n) {
2 for (int i = 2; i < n; i++) {
3 i *= 2;
4 printf("%i
", i);
5 }
6}解答：
假设循环次数为 t，则循环条件满足 2^t < n。 可以得出，执行次数t = log(2)(n)，即 T(n) = log(2)(n)，可见时间复杂度为 O(log(2)(n))，即 O(log n)。
3，递归
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2021-08-06，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
