Chinaunix首页 | 论坛 | 博客
  • 博客访问: 424179
  • 博文数量: 23
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 233
  • 用 户 组: 普通用户
  • 注册时间: 2017-11-28 16:33
文章分类

全部博文(23)

文章存档

2020年(3)

2019年(9)

2018年(10)

2017年(1)

我的朋友

分类: 其他平台

2019-09-20 10:53:17

    一段代码质量的好坏,既有外在的也有内在的,外在的指的就是外表,代码的整洁性、可读性、可维护性等等,而内在就是所指应用的算法,所谓算法是程序的灵魂就是这么来的。在学习算法的过程中,起步你就得知道什么是算法的效率,效率从两方面讲,时间和空间。日常生活中,人们都是愿意以少少的投资获取大大的回报,程序也是如此。
     程序中有一个规范去衡量代码的效率,那就是大O表示法,至于什么叫大O表示法,大O表示法的原理,这篇文章不会细讲,这里主要讲解如何很快的计算出程序的复杂度。首先,给大家列举几个常见的数量级函数:

以下是每个函数当n无穷大时,效率对比图:

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n)< O(n!)< O(n^n)
1.O(n)
一般情况下,程序中没有循环的都可以认为是常数函数,时间复杂度就是O(1)。
2.O(logn)
当存在while函数时,通常就是对数函数,这个循环的时间复杂度就是 O(logn)。
3.O(n^m)
当存在双层for循环的时候,即把 O(n) 的代码再嵌套循环一遍,它的时间复杂度就是 O(n?) 了,以此类推,三层循环就是O(n^3)。
4.O(nlogn)
将时间复杂度为O(logn)的代码循环N遍的话,那么它的时间复杂度就是 n * O(logn),也就是了O(nlogn),就是for循环中有while循环。
     一般的像O(n^3)、O(2^n)O(n!)这样的函数,除非时很小的n的值,否则哪怕n只是100,都是噩梦般的运行时间,所以这种不切实际的算法时间复杂度,我们不去讨论。

阅读(2463) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~