【草稿】时间复杂度如何计算

如何计算时间复杂度

for(i=1;i<=n;i++)//循环了(n+n-1+n-2+...+1)≈(n^2)/2，因为时间复杂度是不考虑系数的，所以也是O(n^2)
   for(j=i;j<=n;j++)
        s++;

排序法

      最差时间分析       平均时间复杂度    稳定度   空间复杂度
冒泡排序    O(n2)       O(n2)            稳定         O(1)
快速排序    O(n2)       O(n*log2n)        不稳定       O(log2n)~O(n)
选择排序    O(n2)       O(n2)            稳定       O(1)
二叉树排序  O(n2)        O(n*log2n)        不一顶        O(n)
插入排序    O(n2)       O(n2)            稳定       O(1)
堆排序      O(n*log2n) O(n*log2n)     不稳定      O(1)
希尔排序    O            O              不稳定     O(1)
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容