26-算法解析及优化拓展

2.4.6　算法解析及优化拓展

1．算法复杂度分析

（1）时间复杂度：在该算法中，问题的规模就是会议总个数n。显然，执行次数随问题规模的增大而变化。首先在成员函数setMeet::init()中，输入n个结构体数据。输入作为基本语句，显然，共执行n次。而后在调用成员函数setMeet::solve()中进行排序，易知sort排序函数的平均时间复杂度为O(nlogn)。随后进行选择会议，贡献最大的为if(meet[i].beg>=last)语句，时间复杂度为O(n)，总时间复杂度为O(n +nlogn)= O(nlogn)。

（2）空间复杂度：在该算法中，meet[]结构体数组为输入数据，不计算在空间复杂度内。辅助空间有i、n、ans等变量，则该程序空间复杂度为常数阶，即O(1)。

2．算法优化拓展

想一想，你有没有更好的办法来处理此问题，比如有更小的算法时间复杂度？