时间戳

首页 > 解决方案 > 如何以渐近方式对以下数据进行排序？

time-complexity - 如何以渐近方式对以下数据进行排序？

问题描述

嘿，伙计们，请在这里帮帮我，我不知道该怎么做，我很快就会提交

a1(n)=5,
a2(n)=2^nlogn,  
a3(n)=n^100
a4(n)=n^n
a5(n)=n!
a6(n)=(0.5)^log(base2)n

标签： time-complexitybig-ocomplexity-theorylower-boundupperbound

解决方案

  • a6(n) = (0.5)^log(base 2)n 随着 n 的增加向 0 递减；因此，这是 O(1)，因为它最终小于任何正常数。应该有可能获得更严格的界限，但这在算法分析上下文中没有用。
  • a1(n) = 5 是一个常数函数，因此 O(1)。
  • a3(n) = n^100 是一个多项式函数，并且比上面的 O(1) 函数渐近地更大。多项式函数在渐近上小于以下指数和阶乘函数。
  • 如果 a2(n) = (2^n)logn，则它小于其他两个。要看到这一点，请尝试 n = 1000 并注意其他两个中有多少更大的因子。
  • a5(n) = n！渐近地小于 n^n，因为两者具有相同数量的项，但 n^n 的因子几乎在每种情况下都更大。
  • a4(n) = n^n 是最大的。如果 a2(n) = 2^(nlogn) 则 a2(n) = a4(n) = n^n 通过代数操作。

推荐阅读