时间复杂度与空间复杂度(小白向)

🤖💻👨‍💻👩‍💻🌟🚀

🤖🌟 欢迎降临张有志的未来科技实验室🤖🌟

专栏：数据结构

👨‍💻👩‍💻 先赞后看，已成习惯👨‍💻👩‍💻

👨‍💻👩‍💻 创作不易，多多支持👨‍💻👩‍💻

🚀 启动创新引擎，揭秘C语言的密码🚀

大O表示法

时间复杂度

打印数组

二分查找

空间复杂度

常数空间复杂度 O(1) 示例：交换两个变量的值

线性空间复杂度 O(n) 示例：数组复制

对数空间复杂度 O(log n) 示例：斐波那契数列（递归版）

优化策略

大O表示法

大O表示法的字母O是函数的增长率，也被称为函数的阶数，即字母O代表Order(阶数)。用大O符号描述函数通常只提供函数增长率的一个上界

常见的有：O(1)，O(n)，O(n²) ，O(nlogn)，O(logn)。

时间复杂度

时间复杂度和空间复杂度是计算机科学中用于评估算法效率的重要指标。这两个概念可以帮助我们了解算法在时间和空间方面的需求，从而优化算法以提高其性能。

时间复杂度：也称为时间复杂度和时间频度，是一个用于描述算法执行时间随输入规模增长而增长的量级。具体来说，时间复杂度是一个函数，它定性描述一个算法的运行时间。

计算时间复杂度的方法如下：

确定算法中的基本操作。
计算基本操作执行的次数。
确定时间复杂度的表示方式。

打印数组

#include <stdio.h>

void print(int* arr, int size)
{
	for (int i = 0; i < 2*size; i++)
		printf("%d ", arr[i]);
}

int main()
{
	
	return 0;
}

函数实现了打印数组的功能，用函数表示上述函数的运行次数就是 y = 2*x，时间复杂度O(n)。

思考：为什么运行2*size次，但时间复杂度不是O(2N)而是O(N) ？

答：目前大多数家用计算机的CPU运算速度大约为每秒50亿次计算，计算10次和20次区别不大。我们可以将 n 看做无穷大（∞），2*n 与 n 没有区别，所以我们索性看做O(n)

二分查找

int binarySearchWithLoop(int arr[], int n, int x) {
    int left = 0;
    int right = n - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        // 如果x是中间元素
        if (arr[mid] == x)
            return mid;
        
        // 如果x小于中间元素，只在左半部分继续寻找
        if (arr[mid] > x)
            right = mid - 1;
        else
            // 如果x大于中间元素，只在右半部分继续寻找
            left = mid + 1;
    }
    
    // 如果x不在数组中
    return -1;
}

经典的二分查找，left 和 right每一次循环直走一步，用函数表达就是n=2^k，k表示运行的次数，由此我们可以得到 𝑘=log2n。时间复杂度为O（logN），这里省略底数与上文同理。

空间复杂度

当我们理解时间复杂度后，学习空间复杂度变得容易许多。

概念：用于描述执行算法所需的内存空间。空间复杂度主要取决于算法在执行过程中所使用的额外空间

常数空间复杂度 O(1) 示例：交换两个变量的值

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

额外空间只有temp一个变量，所以空间复杂度为O(1)。

线性空间复杂度 O(n) 示例：数组复制

void copyArray(int src[], int dest[], int n) {
    for(int i = 0; i < n; i++) {
        dest[i] = src[i];
    }
}

该函数复制一个长度为n的数组到另一个数组中，需要额外的数组dest[]用于存储结果，因此其空间复杂度为O(n)。

对数空间复杂度 O(log n) 示例：斐波那契数列（递归版）

int binarySearch(int arr[], int l, int r, int x) {
    while (l <= r) {
        int m = l + (r - l) / 2;
        if (arr[m] == x)
            return m;
        if (arr[m] < x)
            l = m + 1;
        else
            r = m - 1;
    }
    return -1;
}

二分查找中，虽然没有显式的对数级的额外空间，但递归调用栈的深度为O(log n)，因此在考虑递归空间时，整体的空间复杂度也是O(log n)。