时间复杂度与空间复杂度
衡量一个程序的好坏是看时间复杂度与空间复杂度的!这个是对的吧?!
但是 时间复杂度与空间复杂度 是什么为标准的呢?!!
什么叫时间复杂度
什么叫空间复杂度呢?!
时间的还好理解点.关键是空间..
另外 大家有什么经验呢 对减少时间和空间的复杂度!
[130 byte] By [msdn] at [2007-8-14 12:47:46] 
# 3 Re: 时间复杂度与空间复杂度
时间复杂度指算法的关键操作执行的次数，而空间复杂度指算法所需要的额外空间的数理，不包括提供数据是所占用的空间
xuzheng318 at 2005-5-4 13:15:04 >
# 5 Re: 时间复杂度与空间复杂度
我想做个比方...
比如能用int 形的数据
就不用浮点形的数据
因为这占有的内存少.*********这样是减少了空间复杂度呢?!
还是尽量让程序代码少一些...是减少了空间复杂度?!
Non_miracle at 2005-5-4 13:48:43 >
# 6 Re: 时间复杂度与空间复杂度
时间复杂度不是相对于程序而言的，而是指问题的复杂
例如排序，对分查找在最劣情况下也是平方问题，但对于绝大多数问题而言，我们只关心平均效率。
例如稀疏数组，可以降低对空间的要求，但当有用数据超过一定规模，运行速度将急剧下降。
次数超过4的多项式没有平凡解，所以被成为大O的N次方问题，这样的问题总是需要那么多时间才能完成计算，这就是时间的复杂度。
任何数据的压缩都有极限，越是随机的数据，越不能找到良好的数据结构，这就是空间的复杂性。
实际上如果没有好的算法和数据结构，大多数程序是无法真正做到应用的。
shurufa at 2005-5-4 14:19:17 >
# 8 Re: 时间复杂度与空间复杂度
实际上如果没有好的算法和数据结构，大多数程序是无法真正做到应用的。
这句话是说...大多数的程序都时间和空间的复杂度 是达不到要求的..
是么?!
Non_miracle at 2005-5-4 14:51:39 >
# 11 Re: 时间复杂度与空间复杂度
一旦问题大型化了，复杂化了，时空复杂度应如何计算呢。比如我用STL，他的一个排序，我怎么去算这个黑盒的时空复杂度？从而我也确定不了我自己程序的时空复杂度啊
高手请赐教
aresfe at 2005-5-4 21:00:59 >
# 12 Re: 时间复杂度与空间复杂度
时空复杂度概念上就如忧郁王子所说。
几乎所有算法的设计不外乎在时间复杂度和空间复杂度间找到一个最佳平衡点
tiger999 at 2005-5-4 21:16:07 >
# 13 Re: 时间复杂度与空间复杂度
时间复杂度大概就是程序执行的次数 这个程序大了比较麻烦计算 不过递归有固定的方法 可以查看看数据结构方面的书 清华大学的叶乃菁版讲的不错，空间复杂度是讲执行一个程序所需要的额外的空间 比如交换两个变量时，设了第三个变量，那么它的空间复杂度就是O(1)
wzlno1 at 2005-5-4 22:39:21 >
# 14 Re: 时间复杂度与空间复杂度
关键还是怎么判断关键操作的次数阿？
如果程序刚开始，关键操作经常被执行，随着循环次数增大，关键操作被执行的几率越来越小。那怎样判断？
fire314159 at 2005-5-5 13:25:33 >