第十章 某些算法的分析

一、线性结构相关时间复杂度分析

1、顺序表

访问O(1)、顺序查找O(n)、折半查找O(log2n)插入删除:O(n)


2、链表

访问O(n)、顺序查找O(n)、插入删除(事先直到插入删除的位置):O(1)

二、非线性结构相关的时间复杂度分析

1、树

遍历O(n)

2、图

(1)邻接矩阵:遍历O(n2)   Prim O(n2)

(2)邻接表:遍历O(n+e)

(3)Kruskal O(eloge)
(4)Dijkstra O(n2)    Floyd O(n3)

三、汉诺塔问题(递归、分治)

void hanoi(int n,char a,char b,char c)
{
    if(n==1)
        std::cout<<a<<"->"<<c<<std::endl;
    else
    {
        hanoi(n-1,a,c,b);
        std::cout<<a<<"->"<<c<<std::endl;
        hanoi(n-1,b,a,c);
    }
}
复杂度分析:写递归函数!T(n)=2T(n-1)+c=T(2n)
四、排序算法的性能分析
希尔排序:增量每次都除以二并向下取整,O(n2)。增量取2k+1




全部评论

相关推荐

找到实习了&nbsp;给了150一天&nbsp;但是说是低代码&nbsp;值得去吗
码农索隆:是在没实习,可去,待个一两周,不行就润呗
点赞 评论 收藏
分享
机械打工仔:我来告诉你原因,是因为sobb有在线简历,有些HR为了快会直接先看在线简历,初步感觉不合适就不会找你要详细的了
投了多少份简历才上岸
点赞 评论 收藏
分享
代码飞升:别用口语,后端就写后端,前端就写前端,最后别光后悔
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-08 13:05
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务