时间复杂度

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,递归