内容提示:第01章 函数与极限习题詳解
文档格式:PDF| 浏览次数:17| 上传日期: 23:41:50| 文档星级:?????
全文阅读已结束如果下载本文需要使用
讨论最坏情况下时间复杂度:
大家討论一下O(1)和O(2)的区别!
复杂度是用来表达算法的复杂程度跟算法输入的规模N的关系如果不管N是多大,算法的复杂程度都固定是1或者2(比如1条指令2个循环),那么在“复杂度”这个概念上两者都一样,叫做“常数阶”复杂度比如访问一个数组的元素就是常数阶复杂度,因為不管数组多长访问其中某个元素都是可以通过首地址加一个偏移量来完成。
O(1)这个应该是时间复杂度为常量~
这个应该也是常量级的~~~
O(n)这个表示复杂度为n~~
哦对,常量复杂度就表示为O(1)这个是有的,前面说错了
比常数复杂度复杂一些的,常见的是对数阶复杂度即O(logn),比如有序数组的二分查找;
然后常见的有O(n)比如链式表的随机访问;
然后是,O(nlogn)比如某些排序算法;
有些算法特别复杂,复杂度可能是O(n!)O(n^n)等等。
吔没有“O(n/2)”这么种说法
不过似乎也可以这样理解:
但是还是没有这样说的啊~~~
O(1)常数时间,一般与问题规模无关都采用这一种记法当然如果想写O(2),O(3).....都可以
讨论这种问题没什么意义
那就是说O(2)和O(1)复杂度相同,但代价大些