C语言---数据结构（1）--时间复杂和空间复杂度计算

 

1.什么是时间复杂度和空间复杂度

1.1算法效率

算法效率分为时间效率和空间效率

时间效率被称为时间复杂度，而空间效率被称作空间复杂度。 时间复杂度主要衡量的是一个算法的运行速度，而空间复杂度主要衡量一个算法所需要的额外空间，在计算机发展的早期，计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展，计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度，现在主要关注的是空间效率

1.2时间复杂度的概念

时间复杂度的定义：在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运

行时间。一个算法执行所耗费的时间，从理论上说，是不能算出来的，只有你把你的程序放在机

器上跑起来，才能知道。但是我们需要每个算法都上机测试吗？是可以都上机测试，但是这很麻

烦，所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比

例，算法中的基本操作的执行次数，为算法的时间复杂度。

1.3 空间复杂度的概念

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度 。空间复杂度不是程序占用

了多少bytes的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。空间复杂度计

算规则基本跟实践复杂度类似，也使用大O渐进表示法。

2.如何计算常见算法的时间复杂度和空间复杂度

时间复杂度不算时间，算次数，空间复杂度不算空间，算变量个数

时间复杂度的计算

实际中我们在计算时间复杂度时，我们其实并不一定要计算精确的执行次数，只需要大概执行次数，那么我们这里就使用大O的渐进表示法

大O符号：是用于描述函数渐进行为的数学符号

推导大O阶方法：

1、用常数1取代运行时间中的所有加法常数。

2、在修改后的运行次数函数中，只保留最高阶项。

3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。

使用大O的渐进表示法以后，

另外有些算法的时间复杂度存在最好、平均和最坏情况：

最坏情况：任意输入规模的最大运行次数(上界)

平均情况：任意输入规模的期望运行次数

最好情况：任意输入规模的最小运行次数(下界)

例如：在一个长度为N数组中搜索一个数据x

最好情况：1次找到

最坏情况：N次找到

平均情况：N/2次找到

在实际中一般情况关注的是算法的最坏运行情况，所以数组中搜索数据时间复杂度为O(N)

比如后面的计算strchr的时间复杂度

// 请计算一下Func1基本操作执行了多少次？
void Func1(int N)
{
    int count = 0;
    for (int i = 0; i  
Func1的时间复杂度为：O（N6^2）
 
我们会发现大O的渐进表示法去掉了那些对结果影响不大的项，简洁明了的表达了代码执行的次数
 
// 计算Func2的时间复杂度？
void Func2(int N)
{
    int count = 0;
    for (int k = 0; k  
我们要求去掉N前面的2，随着N的变大，前面的2对结果的影响不是很大，所以去掉
 
那么这个代码的时间复杂度就是O(N)
 
// 计算Func3的时间复杂度？
void Func3(int N, int M)
{
    int count = 0;
    for (int k = 0; k  
这个代码存在多个未知的值，M和N,那么这个复杂度就要根据这个M和N的大小进行比较了
 
// 计算Func4的时间复杂度？
void Func4(int N)//这个N我们没有用到
{
    int count = 0;
    for (int k = 0; k  
因为这个代码是没有用到未知数的，循环的次数仅仅只是一个常数，那么这个题的时间复杂度我们就用O（1）表示，将常量用1来替换
 
// 计算strchr的时间复杂度？
const char* strchr(const char* str, char character)
{
    //遍历字符串中'\0'之前的字符，
    while (*str != '\0')
    {
        if (*str == character)//将这个指针指向的字符和传过来的字符进行判断
            //如果是一样的字符，那么我们就返回这个字符的位置
            return str;
        ++str;//指针++，换下一个字符进行判断
    }
    return NULL;//走到最后都没找到，我们就直接返回一个空指针
}
//这个函数是我们在字符串里面找到我们想要的字符
//那么这个题的时间复杂度怎么说呢？
/*
* 假设这个字符串的长度是N
那么就存在三种可能性：最好、最坏、平均
最坏：就是运行N次才找到                   O（N）
平均：进行到一半才找到                    O（N/2）
最好：一个常数下，假如5次、1次就找到了    O（1）
但是在实际中一般情况关注的是算法的最坏运行情况
所以数组中搜索数据的这个题的时间复杂度是O（N）
我们做出最坏的打算，但是这里也是最靠谱的
*/
/*
做出拓展
1.我们现在给出一个字符串，是长还是短，这个字符串的长度都是不变的
那么这个题时间复杂度就是O（1），效率是不变的
2.如果时间复杂度是O（N）的话，是表达的什么呢？
N就是字符串的长度，随着字符串的变长，这个题目的效率也线性的变长了
*/
 
这里我们用到了最坏运行情况，在这个字符串中找了N次才找到我们想要的字符
 
// 计算BubbleSort的时间复杂度？
void BubbleSort(int* a, int n)
{
    assert(a);
    for (size_t end = n; end > 0; --end)
    {
        int exchange = 0;
        for (size_t i = 1; i  a[i])
            {
                Swap(&a[i - 1], &a[i]);
                exchange = 1;
            }
        }
        if (exchange == 0)
            break;
    }
}
/*
我们先来归纳一下冒泡排序的思想：
在这个数组中，如果第一个数大于第二个数，那么就将这两个数的位置进行交换
将大的数字放后面，小的数字放前面
第一趟冒泡N
第二趟冒泡N-1
第三趟冒泡N-2
第N趟冒泡1
那么这里的次数就是首项+尾项乘以项数除以二
（N+1）*N/2=(N*N+N)/2
上面就是这道题准确的次数
但对于结果影响最大的一项是N^2,因为上面将表达式分解了，所以最大影响的是N方
那么表达就是O（N^2）
这个是阶乘，我们将阶乘的每一项加起来就是这个准确次数了
*/
 
这个是阶乘，我们将阶乘的每一项加起来就是这个准确次数了，
 
不是说一层循环就是O(N),两层循环就是O(N^2)
 
具体看程序，最好通过过程去分析
 
// 计算BinarySearch的时间复杂度？
//二分查找
//二分查找的前提是数组是有序的
int BinarySearch(int* a, int n, int x)
{
    assert(a);
    int begin = 0;
    int end = n;
    while (begin > 1);
        if (a[mid]  x)
            end = mid;
        else
            return mid;
    }
    return -1;
}
/*
最好的情况：O(1)
假设找了x次
1*2*2*2*2*2.....找了多少次就乘了多少次2
最后的结果就是这整个数组的长度
2^x=N
所以次数x就是log2N--以2为底N的对数
那么对于这个题的话
算法的复杂度计算，喜欢省略写成logN,将2省略掉，因为很多地方不好写底数
有些书本，或者网上资料会写成O（lgN），严格来说这个是不对的，因为
这个底数就是10，不符合
那么时间复杂度就是O（logN）
*/
 
// 计算阶乘递归Factorial的时间复杂度？
//这道题实现阶乘递归
long long Factorial(size_t N)
{
    return N  
常见的时间复杂度：O(N^2) O(N) O(logN) O(1)
 
复杂度对比
 
 
 
 
O(1)就是随着这个数量的增加，他是一直都是不变的
 
二分查找，在一个中国有14亿人中找一个人，最多找几次
 
31次就行 2的30次方是10亿，那么2的31次方就是20亿人
 
空间复杂度的计算
 
空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度 。空间复杂度不是程序占用
 
了多少bytes的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。空间复杂度计
 
算规则基本跟实践复杂度类似，也使用大O渐进表示法，类似时间复杂度的方式，也是估算
 
总结：时间复杂度不算时间，算次数，空间复杂度不算空间，算变量个数
 
// 计算BubbleSort的空间复杂度？
void BubbleSort(int* a, int n)
{
    assert(a);
    for (size_t end = n; end > 0; --end)
    {
        int exchange = 0;
        for (size_t i = 1; i  a[i])
            {
                Swap(&a[i - 1], &a[i]);
                exchange = 1;
            }
        }
        if (exchange == 0)
            break;
    }
}
/*
size_t end = n
int exchange = 0
size_t i = 1
三个变量
因为这里的3是常数，那么我们就用1将3代替
那么空间复杂度就是O(1)
循环走了N次，重复利用的是一个空间
*/
 
// 计算Fibonacci的空间复杂度？
long long* Fibonacci(size_t n)
{
    if (n == 0)
        return NULL;
    long long* fibArray = (long long*)malloc((n + 1) * sizeof(long long));
    fibArray[0] = 0;
    fibArray[1] = 1;
    for (int i = 2; i =numsSize，旋转次数大于数组元素个数的话，我们就将k的值取模
*/
void Reverse(int* nums, int left, int right)//对数组的一段区间进行逆置
{
    /*
    1 2 3 4
    1和4交换，2和3交换，最开始的left指向1，right指向4，交换完成之后，；left++,right--,再进行2和3的交换
    */
    while(left=numsSize)
    {
        k%=numsSize;
    }
   Reverse(nums,numsSize-k,numsSize-1);//先将后K个进行逆置
   Reverse(nums,0,numsSize-k-1);//将剩下的N-K个元素进行逆置
   Reverse(nums,0,numsSize-1);//将整体进行逆置
}