首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往
  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    算法基础-函数渐近

    渐近等价 考虑函数: f(x)=x²+4x 当x→∞时,该函数可以看作x平方与它的高阶无穷小o(x²)之和,即 于是我们称f(x)和x²是渐近等价的。...用符号表示为 更一般地,如果存在两个函数f(x)和g(x),使得 你也可以用极限的方法来判断两个函数是否渐近等价 我们可以轻而易举地得到一个结论:f(x)总是跟自己渐近等价 渐近上界 若对于函数...f(n),g(n),存在c和k,使得 即从k开始,f(n)永远无法超过cg(n),则称g(n)为f(n)的渐近上界,写作 注意O(g(n))表示的是一个集合,它代表了所有以g(n)为渐近上界的函数...execute4(i,j); } } 那么此时算法执行命令的总次数就翻了4倍 随着n的逐渐增大,这两个算法所用时间的增长规模是相似的,并且我们并不需要特别高的精度 因此我们可以用算法执行时间...t(n) 的渐近上界 f(n) 来表示一个算法的效率 在渐近时间复杂度中,我们只关心执行时间的增长规模,而不关心具体数字,显然以下两个函数的规模是一致的 因此我们需要对渐近时间复杂度进行化简 函数推导

    64120
    领券