1. 案例1：

    1
2
3
4
5

    public void test1(){
    for(int i=0;i<100;i++){
        System.out.print(i+" ");
    }
}

    无论输入参数的大小，循环次数都是固定的，所以时间复杂度为 O(1)

  2. 案例2：

    1
2
3
4
5

    public void test2(int n){
    for(int i=0;i<n;i++){
        System.out.print(i+" ");
    }
}

    循环次数与输入参数n的大小成正比，所以时间复杂度为 O(n)

  3. 案例3：

    已知一个算法的时间复杂度递推公式为 T(n)=T(n-1)+1 , T(1)=1,求该算法时间复杂度

    由公式可得 T(n)=T(n-2)+1+1=T(1)+…+1+1=n 所以该算法时间复杂度为 O(n)

  4. 案例4:

1
2
3
4

n = 100
i = 1
while i<n:
    i = i*2

在while循环中，变量i每次乘以2 ，设循环次数为 k，则有 $2^k\geq n$ ,解得 $k \geq log_2n$ ,所以循环次数是对数级别的，时间复杂度为 O($logn$)

  1. 案例5：

    1
2
3
4
5
6

    def func(n):
    count = 0
    for i in range(n):
        for j in range(i):
            count = count+1
    return count

    外层循环执行 n 次，对于外层循环的第 i 次，内层循环执行 i 次。总的执行次数为$ \sum_{i=1}^{n-1}i=\frac{n(n-1)}{2} $ ,根据大 O 表示法，忽略常数和低阶项，时间复杂度为 O($n^2$)

  2. 案例6(递归二分搜索)：

     1
 2
 3
 4
 5
 6
 7
 8
 9
10

    def binary_search_recursive(arr, target, low, high):
    if low > high:
        return -1
    mid = (low + high) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] > target:
        return binary_search_recursive(arr, target, low, mid - 1)
    else:
        return binary_search_recursive(arr, target, mid + 1, high)

    这是一个递归实现的二分查找算法。每次递归调用都会将查找范围缩小一半，设问题规模为n ,每次递归后问题规模变为原来的 $\frac{1}{2}$ 。设递归次数为 k ,则有 $ n \times (\frac{1}{2})^k =1 $,解得 $ k = log_2n$,所以时间复杂度为 O($logn$)

  3. 案例7：若某算法的时间复杂度为 $ T(n) = 2T(n/2) + n^2 ,T(1)=1 $，则该算法的时间复杂度为？

  4. 案例8：

    1
2
3
4
5

    def func(n):
    if n <= 1:
        return 1
    else:
        return func(n-1)+func(n-1)

  5. 案例9：

    分析下面嵌套循环代码的时间复杂度，其中 is_prime 函数用于判断一个数是否为素数，其时间复杂度为 $ O(\sqrt{n})$

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

    def is_prime(num):
    if num < 2:
        return False
    for i in range(2, int(num**0.5) + 1):
        if num % i == 0:
            return False
    return True

n = 100
for i in range(n):
    if is_prime(i):
        for j in range(i):
            print(j)
    • 外层 for 循环执行 n 次，对于每次循环，调用 is_prime(i) 函数 ，该函数时间复杂度为 $ O(\sqrt{n})$
    • 当i为素数时 ，内层 for 循环执行 i 次
    • 素数定理表明，小于等于 n 的素数个数约为 $\frac{n}{lnn}$ 。对于每个素数 i ,总的操作次数约为 $\sum_{i是素数且i<n}i$,由于素数判断的时间复杂度为 $O(\sqrt i)$ ,综合考虑，整个代码的时间复杂度为 $O(n^{1.5})$ 。具体分析：外层循环 n 次，对于每个数进行素数判断 $O(\sqrt{n})$,对于素数再进行内层循环，平均来看，整体复杂度是 $O(n\times\sqrt{n})=O(n^{1.5})$