LeetCode 时间复杂度和空间复杂度粗略计算

#创作灵感#

刷LeetCode时需要关注的两点：时间复杂度和空间复杂度。

时间复杂度：程序的运行时消耗的时间

时间复杂度是一个函数，他定性描述了算法的运行时间。

《算法导论》给出的解释是： O用来表示上界，当用他作为算法在最坏情况下运行时间的上界时，就是对任意数据输入的运行时间的上界。

插入排序的时间复杂度是O(n^2)。在数据有序的情况下，插入排序的时间复杂度是O(n)，在数据逆序的情况下是O(n^2)，即最差情况下是O(n^2)。

 快速排序的时间复杂度是O(logn)，但是在数据有序的情况下，快速排序算法时间复杂度是O(n^2)，所以从O的定义来书，快速排序的时间复杂度应该是O(n^2)， 但是我们依然说快速排序的时间复杂度是O(logn)，这就是业内的一个默认规定，这里的O就是一般情况，而不是严格意义上的上界。

空间复杂度：程序运行时占用的内存空间大小

空间复杂度（Space Complexity）是对一个算法在运行过程中占用的内存空间大小的度量，基于空间复杂度可以预先估计程序运行时需要多少内存。

空间复杂度不考虑程序（比如可执行文件）的大小，只考虑程序运行时占用的内存大小。空间复杂度不可以准确计算出程序运行时占用的内存值，因为很多因素会影响程序真正使用的内存大小，比如编译器的内存对齐方式（内存对齐、非内存对齐），编程语言容器的底层实现都会影响程序内存的开销。所以空间复杂度仅仅是大致评估程序内存使用情况。

内存对齐方式：CPU读取内存时不是一次读取单个字节，而是按照块来读取，块的大小可以是2,4,8,16字节，具体读取多少取决于硬件。

假设CPU把内存划分为4字节大小的块，要读取一份4字节大小的int32型数据，对比下两种内存对齐方式的不同（char占1字节，int32 占4字节）：

•  内存对齐：只需要一次寻址即可

 1字节的char占用4字节的内存空间，空了3字节的内存地址，int数据从地址4开始，此时直接读取4,5,6,7处的4字节数据即可。

• 非内存对齐：需要两次寻址，外加一次合并

char数据和int32数据挨在一起，该int32数据从地址1开始，CPU读取这个int32数据需要一下步骤：

1. CPU读取0,1,2,3处的4字节数据

2. CPU读取4,5,6,7处的4字节数据

3. 合并地址1,2,3,4处后的4字节的数据才是背刺操作需要的int32数据。

以下三种不同的例子描述下空间复杂度和时间复杂度。

递归算法的空间复杂度计算公式：每次递归的空间复杂度 * 递归深度。

递归深度： 因为每次递归所需的空间都被压到栈里面，一次递归结束后，当前递归的数据会从栈中移除（弹出去），所以栈的最大长度(时间复杂度为O(n))就是递归的深度。

每次递归的空间复杂度在递归算法中基本上是一致的，所需要的空间是一个常量，并不会随着n的变化而变化，所以每次递归的空间复杂度是O(1).

PS:版本二中的Fibonacci(second, first + second, n-1);会导致时间复杂度变成O(n^2)

// 版本1-利用 迭代 计算斐波那契
int Fibonacci(int n)
{
    if (n <= 0)
    {
        throw new ArgumentException("Input must be a non-negative integer.");
    }
    else if (n == 1)
    {
        return 0;
    }
    else if (n == 2)
    {
        return 1;
    }

    int a = 0; // F(0)
    int b = 1; // F(1)
    int fib = 0;

    for (int i = 3; i <= n; i++)
    {
        fib = a + b;
        a = b;
        b = fib;
    }

    return fib;
}


// 版本2-利用 常规递归 计算斐波那契
int Fibonacci(int n)
{
    if (n <= 0) return 0;
    if (n == 1) return 1;
    return Fibonacci(n - 1) + Fibonacci(n - 2);
}

// 版本3-利用 优化后的递归 计算斐波那契
int Fibonacci(int first, int second, int n)
{
    if (n <= 0) return 0;
    if (n < 3) return 1;
    else if (n == 3) return first + second;
    else
    {
        return Fibonacci(second, first + second, n-1);
    }
    
}

二分查找的时间复杂度和空间复杂度都是O(logn).

递归函数传递的数组参数是首元素地址而不是整个数组，也就是说每次递归都公用一块地址空间，所以每次递归的空间复杂度是一个常数O(1)。二分查找递归的深度是logn，递归深度就是调用栈的长度，那么二分查找的空间复杂度即 O(1*logn)=O(logn).

int BinarySearch(int arr[], int l, int r, int x)
{
    if (r >= 1)
    {
        int mid = l + (r - 1) / 2;
        if (arr[mid] == x)
        {
            return mid;
        }
        if (arr[mid] > x) 
        {
            return BinarySearch(arr[], l, mid - 1, x);
        }
        else
        {
            return BinarySearch(arr[], mid + 1, r, x);
        }
    }
    return -1;// 未找到
}