博文

算法多项式时间复杂度是天大的笑话！

已有 5194 次阅读 2015-6-6 01:48 |个人分类:科研讨论|系统分类:科研笔记| 笑话, 算法多项式时间复杂度

算法多项式时间复杂度是天大的笑话！

姜咏江

Email: accsys@126.com

任何一个非零自然数x都可以写成的多项式形式，其中a_i取值0或1。那么任意x^k=，

于是有O(x^k)=O(2^nk)，此处n是一个变量。多项式时间变成了指数时间！算法多项式时间复杂度难道不是一个天大的笑话？

2015-6-6

转载本文请联系原作者获取授权，同时请注明本文来自姜咏江科学网博客。
链接地址：https://blog.sciencenet.cn/blog-340399-895858.html

上一篇：The algorithm polynomial time complexity is a big joke！
下一篇：科学网的网速为何越来越慢？

收藏 IP: 114.111.166.*| 热度|

IP: 117.169.1.* 回复 | 赞 +1 [4]刘吉斌 2015-6-6 14:11: 不能用任意一个特定的多项式表达式都可以表示为特定的指数表达式，反之也然，来说明它们是同价的。二种表达式的变量是相同的（样本数），问题的实质是它们之间的增长速度的差异是非常大的，也是给定相同的样本增量所导致的计算增量存在非常大的差别。

IP: 117.169.1.* 回复 | 赞 +1 [3]刘吉斌 2015-6-6 13:27: 多项式时间是随样本的增加以O（x^k)的方式增加（k指最高次数），你这O（2^nk)中的n是指样本数？; 姜咏江回复刘吉斌：你的样本是指输入吗？是否包括问题的寓意？如果你看了那篇博文，那么nk无疑是指程序结构与输入相关的循环最高层次数。
2015-6-6 13:381 楼（回复楼主）赞 +1 | 回复

IP: 117.169.1.* 回复 | 赞 +1 [2]刘吉斌 2015-6-6 13:10: 请问你文中x和k是什么关系？; 姜咏江回复刘吉斌：在我请你读的博文中说得很清楚。不在回复中说了，行吗？
2015-6-6 13:191 楼（回复楼主）赞 +1 | 回复

IP: 117.169.1.* 回复 | 赞 +1 [1]刘吉斌 2015-6-6 11:56: 姜老师你搞错了，计算对象的样本数是整数变化的，设x为样本数，O（x^k)可表示多项式时间，O（2^x)可表示指数时间，但你文中O（2^nk)的n是随k的增大而远小于1，这与指数增长不一致。; 姜咏江回复刘吉斌：所谓多项式时间认定k是常数，不是变量，不用谈k增大。你如果知道用数码如何表示数，那么在十进制中也可以有O(x^k)＝O(10^nk)其中n是整数变量，只要整数x>10，n就是一个大于0的整数。例如256^5=(2*10^2+5*10^1+6*10^0)^5,这里k=5,n=2。如果x=65479呢？我想你也会求n是多少。按照大o的表示不考虑低指数项，该如何？
2015-6-6 12:521 楼（回复楼主）赞 +1 | 回复; 姜咏江回复刘吉斌：读一下http://blog.sciencenet.cn/blog-340399-895336.html 如何？
2015-6-6 13:012 楼（回复楼主）赞 +1 | 回复

1/1 | 总计:4 | 首页 | 上一页 | 下一页 | 末页 | 跳转

返回顶部

扫一扫，分享此博文