《算法技术手册》一2.4.7 性能不明显的计算
2.4.7 性能不明显的计算 在很多情况下，仅仅通过算法的描述（如加法和乘法）就可以分辨出算法的性能是线性级还是平方级的。例如，平方级的主要特征是嵌入的循环结构。但是，这样的直接分析对某些算法却无法使用。例2-5给出了GCD算法，该算法是由欧几里德设计，用于计算两个整数的最大公约数。例2-5：欧几里...
《算法技术手册》一2.4.1 常数级算法的性能
2.4.1 常数级算法的性能 在分析算法性能时，本书常常会强调原生操作都具有常数级的性能。很明显，这个声明并不能完全准确地描述实际操作的性能，因为它没有考虑到硬件问题。例如，比较两个32 位的数x和y的大小，这个操作耗费的时间与x、y的大小无关。常数级的操作被认为具有O(1)的性能。那么在比较两个2...
《算法技术手册》一3.4.1 性能
3.4.1 性能一个广为接受的观点是整数运算会比浮点运算高效得多。表3-1列出了在高端计算机上进行10 000 000次计算的时间，这些结果包含了本书第1版中在Linux平台上的结果，还有一台1996 年的Sparc Ultra-2的结果。可以看到，单个操作的性能在不同平台上的差异很大。而且从这些结...
《算法技术手册》一2.4.8 指数级算法性能
2.4.8 指数级算法性能 考虑有一种锁，它由3个连续的数字拨盘组成，每个拨盘包含0~9的数字，并且都可以独立设置10个数字中的一个。假如你发现了这种锁，并且没有能将其打开的数字组合。你可能认为这不过是耗费一些体力工作的问题，只要尝试从000~999的1000种组合中可能的每一种即可。为了归纳这个问...
《算法技术手册》一2.4.5 线性对数算法的性能
2.4.5 线性对数算法的性能性能指标很好地描述了同类算法的共同行为。为了更好地阐述算法在实践中的行为，我们定义了一个函数t(n)，用于表示算法解决样本规模为n的问题所需要的时间。分治法是解决问题的一个高效方法，它将规模为n的问题划分成（大致相等的）两个规模为n/2的子问题，并通过递归解决问题。这些...
《算法技术手册》一2.4.4 线性算法的性能
2.4.4 线性算法的性能 要得到某些问题的解明显需要更多的努力。一个孩子能够计算7 + 5等于12，那么要计算37 + 45会有多难呢？更具体一点来讲，相加两个n位的数an-1...a0 + bn-1...b0得到一个（n + 1）位的数cn...c0有多难？相加算法使用了如下的原生操作：例2-2...
《算法技术手册》一2.4.2 对数级算法的性能
2.4.2 对数级算法的性能 酒保和顾客打了一个10 000 美元的赌。酒保说：“我会从1~1 000 000中挑选一个秘密数字，你有20次的机会来猜这个数字。每次猜完，我会告诉你结果是高了、低了，还是猜中了。如果你能在20个问题之内猜到我的秘密数字，我给你10 000美元，否则你给我10 000美...
《算法技术手册》一2.4.3 次线性级算法O(nd)(d<1)的性能
2.4.3 次线性级算法O(nd)(d<1)的性能 在某些情况下，次线性算法的性能要好于线性算法，但还是不如对数算法高效。第10章将会讨论多维k-d树，它能够高效地划分n个d维的点。如果k-d树是平衡树，那么区间查询的性能为，在二维的情况下，最终性能为O(sqrt(n))。
《算法技术手册》一2.4.6 二次方的算法性能
2.4.6 二次方的算法性能 现在考虑一个类似的问题：两个n位的整数相乘。例2-4展示了使用小学课堂上学过的算法实现的乘法运算，其中n位数字的表示方法与之前的加法一样。 例2-4：mult乘法的Java实现 public static void mult (int[] n1, int[] n2, i...
本页面内关键词为智能算法引擎基于机器学习所生成，如有任何问题，可在页面下方点击"联系我们"与我们沟通。
