- 论坛徽章:
- 8
|
本帖最后由 shan_ghost 于 2013-12-13 15:11 编辑
算法复杂度描述的是，一个算法随着处理对象的数目n的增长，所需时间、空间与n之间的函数关系（的粗略估计）。
假设对一个问题，当处理对象为1时，需要执行X个操作，这些操作的总执行时间是T,执行算法需要的额外空间是S。
那么当处理对象数目为2时，就需要执行f（2） × X 个操作（也就是执行时间为f(2)*T），需要的额外空间就是g(2) × S。
……
依此类推，当处理对象数目为n时，需要执行f(n)×X个操作，需要的额外空间为g(n)×S。
而大O标记法，其实就是函数f(n)/g(n)里面关于n的最高次项。
这是因为，要精确表示f(n)，需要的表达式可能很复杂。比如可能是f(n)=6n^3+7n^2-5n+2 。
显然，随着n的增长（n是自然数），低次项的贡献迅速减小；甚至高次项的系数6,贡献也迅速减小。
另外，这个T也是很随意的、随着机器不同、具体算法不同而剧烈变化（这个后面再说）。
所以，大O标记法只关注n的最高次方项的次方数，并不关注它的系数。
举例来说，2分法查找，当待查找数组中只有一个元素时，只需执行如下逻辑一次：
1、访问第m和n元素之间的中位元素（m/n初始为0和1）
2、比较它的值
3、输出查找成功、或者根据比较结果修改m/n的值
4、检查m/n的值，继续查找或输出失败
而当有N个元素时，就需要执行如上逻辑ln(n)次。
设每次执行如上逻辑需要的时间为T，则时间复杂度为ln(n)×T。
于是，我们就说二分查找法的时间复杂度随n增长的趋势是对数级的，用大O标记法标记为O(ln n)
而无论n有多大，执行如上逻辑，需要的空间数目都没有变化。即总是需要1×S大小的空间，所以空间复杂度为O(1)。
——————————————————
类似的，对于hash_map，当从1个元素中查找某个值时，需要做什么呢？
1、计算hash值
2、根据算出的hash值，直接访问某个内存位置
如果map中的元素数量更多些呢？
答案仍然是：算hash值，然后直接访问。
所以，我们说hash_map的时间复杂度为O(1)的。
但，注意O(1)可未必就等于快！
比如，如果数据只有4个char，我把它直接存数组里；需要时就逐个比较——相比之下，这可是O(n)的蜗牛算法。
但，这个算法只需要做4次比较而已（即Ts=一次比较指令+循环变量自增+跳回循环首部 所需时间之和），大概也就是8到12条机器指令；
而hash呢，光计算hash就得几十条指令了（即Th=几十条指令的执行时间）。
相比之下，hash就慢太多了。
所以，一些规模很小的问题，宁可使用逐个比较或者二分查找，也不要使用hash。得不偿失。
但，当n的规模提高之后，比如n成了一百万，那么逐个比较就需要几百万条指令，而hash呢，仍然只需几十条指令——O(1)算法的威力，现在才能体现出来。
——————————————————————————————
总之，算法的时间复杂度，意思是待处理数据的数量n与所需指令数目之间的函数关系；并不是什么别的神秘的东西。
空间复杂度也类似。
|
|
免费注册
楼主: fender0107401
发表于 2013-12-13 15:04
我也是第一次听说这三个 windows 函数，不也幸好没饿死。