july算法1——算法初步

1.算法复杂度

O(1)
基本运算，＋，－，＊，／，%，寻址
O(logn)
二分查找
O(n^1/2)
枚举约数
O(n)
线性查找
O(n²)
朴素最近点对
O(n³)
Floyd最短路
普通矩阵乘法
O(nlogn)
归并排序
快速排序的期望复杂度
基于比较排序的算法下界
O(2ⁿ)
枚举全部的子集
O(n!)
枚举全排列
总结：
优秀 O(1) < O(logn) < O(n^1/2) < O(n) < O(nlogn)
可能可以优化 O(n²) < O(n³) < O(2ⁿ) < O(n!)

2.从暴力算法开始优化

给定数组a[1…n]，求最大子数组和，即找出1<=i<=j<=n，使a[i]+a[i+1]+…+a[j]最大。

支持：出队，入队，求最大元素
要求O(1)
均摊分析

给定一个正整数组a，是否能以3个数为边长构成三角形？
即是否存在不同的i，j，k，
满足 a[i] < a[j] + a[k]
并且 a[j] < a[i] + a[k]
并且 a[k] < a[i] + a[j]

最后编辑于：2018.10.08 22:42:55

©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成，浏览时请结合常识与多方信息审慎甄别。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。