算法基础笔记_时间复杂度

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了算法基础笔记_时间复杂度，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2976字，纯文字阅读大概需要5分钟。

内容图文

大O的理解：

• n表示数据规模
• O(f(n)) 表示运行算法所需要执行的指令数（运行时间），和f(n)成正比
• O(f(n)) 可以理解为： t = a*f(n) + b = f(n)
• 简单验证程序算法复杂度的方法：将数据规模依次成倍增长，查看运行时间的增长规律，或作出 t-n 的坐标图观察。
• “均摊复杂度” 和 “复杂度震荡”

• 二分查找法 O(logn)                       所需执行指令数：a*logn
• 寻找数组中的最大/最小值 O(n)     所需执行指令数：b*n
• 归并排序算法 O(nlogn)                 所需指令数：c*nlogn
• 选择排序法 O (n^2)                       所需指令数：d*n^2

        O(nlogn+n) = O(nlogn)

        O(nlogn+n^2) = O(n^2)

      数据规模量不一致时：

        O(AlogA+B) != O(AlogA)

        O(AlogA+B^2) != O(B^2)

     对邻接表实现的图的遍历：

     时间复杂度：O(V+E)

         V：顶点个数； E：边的个数

二分查找法的时间复杂度是O(logn)的理解：

     二分查找的执行步骤：在n个元素中寻找 -> 在n/2个元素中寻找 -> 在n/4个元素中寻找 -> ... 在一个元素中寻找

                                         n经过 t 次“除以2”操作后等于1   ->     ->   

    可推：n经过 t 次 “除以k” 的操作后等于1 —> 时间复杂度：

    注： ,   因为 , 而  是一个常数。

 

O(nlogn)的例子：外层循环是一个t次“乘以2”操作到达n的过程，是一个O(logn), 内层循环是一个O(n),故双层循环嵌套后为O(nlogn)

?for(int i=1; i<n; i+=i){
    for(int j=1; j<n; j++){
        //do something
    }
 }

O()的例子：i一步一步到达。

for(int i=1; i*i<n; i++){
    //do something
}

 

递归算法的时间复杂度分析： 

• 递归函数中，只进行一次递归调用，递归深度为depth, 在每个递归函数中，时间复杂度为T，则总体的时间复杂度为O(T*depth)
• 递归函数中，多次进行递归调用，要考虑递归深度、递归调用次数、每个递归函数中的时间复杂度。 具体可查阅“主定理”知识。

参考：各种排序算法性能之间的比较

          o(1), o(n), o(logn), o(nlogn)

一个时间复杂度问题：

      有一个字符串数组，将数组中每一个字符串按照字母排序；之后再将整个字符串数组按照字典序排序，求整个操作的时间复杂度。 

错误解法：O(n*nlogn+nlogn)=O(n^2logn)

正确思路：假设最长的字符串长度为s, 数组中有n个字符串；(排序算法中，nlogn表示的是比较的次数)

                  对每个字符串排序：O(slogs)，而数组中有n个字符串，则：O(n*slogs);

                  将整个字符串数组按照字典序排序：O(s*nlogn)

                  综上：O(n*slogs) + O(s*nlogn) = O(n*s*logs+s*n*logn)

算法复杂度在有些情况下是用例相关的 ：

  插入排序算法O(n^2):                    快速排序算法O(nlogn):                                               

     最差情况: O(n^2);                           最差情况: O(n^2);

     最好情况: O(n);                              最好情况: O(nlogn)

     平均情况: O(n^2)                           平均情况: O(nlogn)

对数据规模的概念： 

   如果想要在1s之内解决问题：

• O(n^2)的算法可以处理大约10^4级别的数据；
• O(n)的算法可以处理大约10^8级别的数据；
• O(nlogn)的算法可以处理大约10^7级别的数据；

  为了保险起见，可以降低一个数量级。

空间复杂度： 

• 多开一个辅助的数组：O(n)
• 多开一个辅助的二维数组：O(n^2)
• 多开常数空间：O(1)   即开一些临时的变量存储一些临时的值，不论数据规模n的大小，开出的存储空间是一定的。

  注意：递归的调用是有空间代价的，递归过程中未退出的状态要压入系统栈中，空间复杂的与递归的深度有关。

内容总结

以上是互联网集市为您收集整理的算法基础笔记_时间复杂度全部内容，希望文章能够帮你解决算法基础笔记_时间复杂度所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---