当前位置：首页 > article >正文

C/C++ 时间复杂度(On)

article 2025/1/22 0:10:03

定义：

在计算机科学中，时间复杂性，又称时间复杂度，算法的时间复杂度是一个函数，它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，亦即考察输入值大小趋近无穷时的情况。

将数字从 1~100 进行排序不同的人用不同的方法写出的程序都会有所偏差，这就需要我们对编写这个算法有一定的预期，了解这部分算法的运行效果，如果运行效果不适用，就没必要使用这个算法。我们不需要知道某种算法具体的执行时间，而是用大O表示法表示时间的概念，也就是时间复杂度。

大O表示法一般就是来表示某个函数的时间复杂度，所以 O 代替了函数名字，括号里面的代数表示
函数参数。
在这里插入图片描述

O(1) ：

每天去上班，只需要和老板一个人打招呼，不管招呼内容是什么，这件事情只需要做一次，每次花费的时间几乎是相等的，我们就可以用 O(1) 来表示这所消耗的时间。

int msg(const char * msg) {
    printf("%s \n", msg); // 需要执行一次
}

这里不管输入的字符串有多大，都是常量，对于程序而言，就只需要执行一次，把每次执行消耗的时间约等于相等，那么用x,y轴的形式来表示就会是一条直线，我们直接O(1)来表示这样的常量时间。
在这里插入图片描述

O(n):

每天去上班，需要和公司所有人都打招呼，就需要你每天和公司这n个人逐个问候，虽然与每个人打招呼时间相同，但是要进行n多次，因此我们就用O(n)来表示。

int msg(int n) {

    for (int i = 0; i < n; i++) {         // 需要执行 (n + 1) 次
        printf("Hello!\n");               // 需要执行 n 次
    }
    return 0;                              // 需要执行 1 次
}

这个函数需要遍历数组里面所有元素，因为数组里每个元素都需要遍历一次，所以数组如果有非常多元素，就需要执行多次，也就可以用 O(n) 来表示。因为很明显是一种线性的时间，如果n越大，也就是这个数组的元素越多。消耗的时间也就是越多的。

O(n²):

公司业务扩招，现在有多个部门，你需要每天上班，先给部门A所有人逐个打招呼，然后再给部门B里面所有人逐个打招呼，剩下所有部门都是这样打招呼，我们就可以用O(n^²)来表示这所耗费的时间，因为你不止要遍历每个部门还要遍历每个部门的人。

void msg(int numberofDepartments, int numberOfPeople) {
    for (int i = 0; i < numberofDepartments; i++) { // 循环次数为 n
        for (int j = 0; j < numberOfPeople; j++) {  // 循环次数为 n
            printf("Hello!\n");        // 循环体时间复杂度为 O(1)
        }
    }
}

也就是嵌套循环，这里一共有多少个部门 numberofDepartments,部门中有多少人 numberOfPeople。比方说有4个部门，每个部门有4个人，那么这里输出打招呼的信息就是 16 次，也就是 4 ² = 16 ,所以用 O(n²) 来表示.

在这里插入图片描述

O(log n)

2¹  = 2
2³  = 8
2⁵  = 32
2¹⁰ = 1024

如果用 log 的形式写:
log₂2 = 1
log₂8 = 3
log₂32 = 5
log₂1024 = 10
这里的  2,8,32,1024 就是 n,这个n即使变得很大，结果并没有等比例增大，就是结果的增速缓慢。每次对半分的话，越到后面，需要消耗的时间相对就越少。

这里 O(log n) 并没有把底数 ₂ 写出来

#include <stdio.h> 
int binary_search(int *arr,int p,int q,int ele) {
    int mid = 0; 
    if (p > q) {
        return -1;
    } 
    mid = p + (q - p) / 2; 
    if (ele == arr[mid]) {
        return mid;
    } 
    if (ele < arr[mid]) { 
        return binary_search(arr, p, mid - 1, ele);
    }
    else { 
        return binary_search(arr, mid + 1, q, ele);
    }
}

int main()
{
    int arr[10] = { 10,14,19,26,27,31,33,35,42,44 };
  
    printf("%d", binary_search(arr, 0, 9, 31));
    return 0;
}