[数据结构与算法]时间复杂度与贪心算法

时间复杂度与贪心算法

14天阅读挑战赛

算法的复杂度

时间复杂度

计算时间复杂度

假设每一条代码执行所用时间相同。

for循环的第一条语句执行n+1次

for循环内部的所有语句执行n*次

算法的运行时间主要取决于最高项，小项和常数忽略不计

并不是所有的算法都可以直接计算时间复杂度

如下代码

int findx (int x){
    for(int i = 0;i<n;i++){//查找
        if(a[i]==x)
            return i;//查找成功返回i
    }
    return -1;//查找失败返回-1
}

由于不知道x在a[i]数组中位置如何，所以很难直接计算算法的时间复杂度。

这样的算法还有很多，比如排序，查找，插入，对于这样的算法，通常考虑最坏的情况而不是最好的情况，最坏情况对衡量算法的好坏有着实际的意义。

常见的几种时间复杂度

• 常数
• 多项式
• 指数（由于指数爆炸式的增长速度，应尽量避免爆炸增量函数，比如递归，可以尝试使用数组来代替递归，但数组的空间复杂度较高，对于运算量小的程序，可以尝试使用迭代法进行运算。eg：斐波那契数列）
• 对数--------对数阶的运行效率高

空间复杂度

只计算辅助空间，即为了完成运算而辅助开辟的空间。忽略算法本身占用空间以及输入输出

什么是辅助空间呢

如下代码

void swap(int x,int y){
    //交换x和y
    int temp;
    temp =x;
    x=y;
    y=temp;//temp即为辅助空间，此外，这种写法放在函数中是错误的，应该通过指针来操控函数外部的空间，局部变量会随着函数的释放而销毁。
}

对于阶乘/递归，每一次对于自身的调用都会进栈，所以阶乘的空间复杂度为O(n)，用T(n)来表示阶乘的空间复杂度为n

贪心算法

贪心算法期望做出当前最好的选择以期望得到全局最优的解决方案

• 一旦做出选择，便不可以回溯
• 有时可能得不到最优解，而是得到最优解的近似解
• 贪心策略直接决定算法的好坏

什么时候可以使用贪心算法

• 贪心选择：问题的最优解可以通过一系列的最优选择得到，这种选择不依赖于未作出的选择
• 最优子结构：问题的最优解包括其子问题的最优解

如何使用

1.确定贪心策略：选择当前最好的方案。

2.局部最优解：分别使用同样的贪心策略得到所有的局部最优解

3.全局最优解：将所有的局部最优解合成即可

实际运用贪心算法

最优装载问题

海盗们截获了一艘古董货船，要求得到最多的古董

• 贪心策略：重量最小者先装

算法设计：如果每次选择一个最小分别装进海盗船，那么此时的时间复杂度是n^{2，所以最优算法应该是先排序再**依次选择**，此时的时间复杂度是nlgn，远远小于n}2。

利用ans记录装入海盗船的古董数量，tmp暂存装入海盗船的重量

int main (int n ){
    sort(w,w+n)//对所有的古董进行排序，升序排序，所以接下来应该从第一个古董w[0]开始取。sort函数默认是升序排列
    double tmp=0.0//目前装入海盗船的古董重量
    int ans = 0;//装入海盗船的古董件数
    for(int i=0;i<n;i++){
        tmp+=w[i];//先将古董上船
        if(tmp<=w)//如果能装下则计数
            ans++;
        else
            break;//如果装不下则不计数
    }
    return ans;
    }
}

时间复杂度分析

sort 函数的时间复杂度为O(nlgn)

此程序的复杂度为O(n+nlgn),n可以忽略不计

空间复杂度分析

此程序的空间复杂度为常数阶，视作O(1)。

课后题

如果想知道装入了哪些古董，怎么实现呢

新建结构体即可

即如下代码

#include <iostream>
struct olds
{
    double weight;
    int num;
}//定义一个古董，并赋予编号num
olds w[10]//定义一个结构体数组，类型为olds
bool cmp(const w &a,const w &b )//const必须加，不然会错
{
    return a.weight>b.weight;//指定weight按照升序排列
}
int main (int n ){
    sort(w,w+10,cmp)//指定使用cmp函数来进行排序
    double tmp=0.0
    int ans = 0;
    for(int i=0;i<n;i++){
        tmp+=w[i];
        if(tmp<=w)
            ans++;
        printf("%d",ans,w[i].num);//只输出编号而不是ans
        else
            break;
    }
    printf("%d",ans);
    }
}

会议安排问题

有一大堆会议需要安排，问如何安排才能在有限的时间内尽可能多的召开会议，会议时间不可以交叉。

贪心策略：从未安排的会议中选择具有最早结束时间且与已安排的会议相容的会议

bool cmp(meet x,meet y){
    if(x.end==y.end)//结束时间相同时
        return x.beg>y.beg;//按照开始时间从早到晚排序
    return x.end<y.end;//按照结束时间从早到晚排序
}