更改

删除57字节 、 2021年9月23日 (四) 19:39
第128行: 第128行:       −
有一个常见的误解,由于'''摩尔定律 Moore's law'''假定了现代计算机功率的'''指数增长 exponential growth''',对算法复杂度的评估将变得不那么重要。这是错误的,因为这种功率增加同样也会容使得处理较大的输入数据('''大数据 big data''')成为可能。例如,当一个人想要按字母顺序对数百个条目的列表进行排序时,比如一本书的'''参考书目 bibliography''',任何算法都应该在不到一秒的时间内就能正常工作。另一方面,对于一个包含100万个条目的列表(例如一个大城镇的电话号码) ,需要<math>O(n^2)</math>次比较的基本算法,须进行1万亿次比较运算,即以每秒1000万次的速度进行比较需要大约3个小时。另一方面,'''快速排序 quicksort'''和'''合并排序 merge sort'''只需要<math>n\log_2 n</math>次比较(前者为平均情况复杂度,后者为最坏情况复杂度)。这大约是3000万次比较,以每秒1000万次比较计算,只需要3秒钟。
+
有一个常见的误解,由于'''摩尔定律 Moore's law'''假定了现代计算机功率的'''指数增长 exponential growth''',对算法复杂度的评估将变得不那么重要。这是错误的,因为这种功率增加同样也会容使得处理较大的输入数据(大数据)成为可能。例如,当一个人想要按字母顺序对数百个条目的列表进行排序时,比如一本书的参考书目,任何算法都应该在不到一秒的时间内就能正常工作。另一方面,对于一个包含100万个条目的列表(例如一个大城镇的电话号码) ,需要<math>O(n^2)</math>次比较的基本算法,须进行1万亿次比较运算,即以每秒1000万次的速度进行比较需要大约3个小时。另一方面,快速排序和合并排序 只需要<math>n\log_2 n</math>次比较(前者为平均情况复杂度,后者为最坏情况复杂度)。这大约是3000万次比较,以每秒1000万次比较计算,只需要3秒钟。
       
因此,对复杂度的评估允许在编程实现之前就消除许多低效率的算法。这也可用于在不用测试所有变量的情况下调优复杂的算法。通过确定复杂算法中最复杂的步骤,对复杂度的研究还可以将重点放在这些步骤上,从而提高实现的效率。
 
因此,对复杂度的评估允许在编程实现之前就消除许多低效率的算法。这也可用于在不用测试所有变量的情况下调优复杂的算法。通过确定复杂算法中最复杂的步骤,对复杂度的研究还可以将重点放在这些步骤上,从而提高实现的效率。
    +
<br>
    
==更多资料==
 
==更多资料==
7,129

个编辑