2.4.9 渐进增长小结
不论实际常数是大是小,拥有较好渐进增长的算法最终会比较差渐进增长的算法执行得更快。真正区分两类算法的性能的转折点会根据实际常量的不同而有所不同,这里的常量是实际存在的并且可以根据经验预估得出。此外,在渐近线分析时,只需要关注t(n)函数中增长最快的部分。出于这个原因,如果一个算法的操作次数为cn3 + dnlog(n),应当将该算法归类为O(n3),因为这部分要比nlog(n)的增长快得多。
2023-11-06 14:51:28
不论实际常数是大是小,拥有较好渐进增长的算法最终会比较差渐进增长的算法执行得更快。真正区分两类算法的性能的转折点会根据实际常量的不同而有所不同,这里的常量是实际存在的并且可以根据经验预估得出。此外,在渐近线分析时,只需要关注t(n)函数中增长最快的部分。出于这个原因,如果一个算法的操作次数为cn3 + dnlog(n),应当将该算法归类为O(n3),因为这部分要比nlog(n)的增长快得多。