你会如何去寻找这个算法的复杂性? [英] How would you go about finding the complexity of this algorithm?

查看:30
本文介绍了你会如何去寻找这个算法的复杂性?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

function alg1(n)
1 a=0
2 for o=1 to n do
3     for t=1 to o do
4         for k=t to o+t do
5         a=a+1
6 return(a)

如果有人能指导我如何在这里找到最坏的情况,以及如何将 alg1 的输出 a 作为 n 的函数,我将不胜感激.谢谢!

If anyone could guide me to how you would find the worst-case here, and how to get the output a of alg1 as a function of n, I would be very grateful. Thanks!

推荐答案

我们可以计算此代码执行的确切增量数.首先,让我们替换

We can compute the exact number of increments this code executes. First, let's replace

for k=t to o+t do

for k=1 to o+1 do 

这个改动后,两个内循环是这样的

After this change, two inner loops looks like this

for t=1 to o do
    for k=1 to o+1 do

这些循环的迭代次数显然是o*(o+1).总迭代次数可以通过以下方式计算:

The number of iterations of these loops is obviously o*(o+1). The overall number of iterations can be calculated in the following way:

当使用大 O 表示法时,我们可以排除多项式的系数和低阶项.因此,复杂度为O(n^3).

We can exclude coefficients and lower order terms of the polynomial when using big-O notation. Therefore, the complexity is O(n^3).

这篇关于你会如何去寻找这个算法的复杂性?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆