0

我正在尝试为今晚到期的项目的一部分掌握 Big O 的想法，我不知道我是否正确地考虑了这一点......

该项目包括我们为数学运算编写迭代和递归解决方案。

这里有一些方法。

public int inc(int n)
{
    n = n + 1;
    return n;
}
public int dec(int n)
{
    n = n - 1;
    return n;
}

public int add(int lhs, int rhs)
{
   int sum = lhs;    
   while (rhs > 0) {
        sum = inc(sum);
        rhs = dec(rhs);
    } // while
    return sum;
}


public int fac(int num)
{
    int ans = num;
    while(num > 1)
        {
            ans = mul(ans, dec(num));
        }
    return ans;
}



public int div(int lhs, int rhs) throws ArithmeticException
{
    int quot = 0;
    while (lhs > 0)
        {
            lhs = sub(lhs,rhs);
    if(lhs < rhs)
                {
        quot = 0;
                }   
            else
                {
                    quot = inc(quot);
              }
        }
    return quot;
}


public int lshift(int lhs, int rhs)
{
    return mul(lhs,pow(2,rhs));       
}

所有这些都是 O(n) 吗？还是只是 inc、dec 和 add？

对于调用其他方法的行（如 mul - multiply - 在 fac 和 lshift 中），这是恒定时间还是再次 n，使得 O(n^2)？有人可以解释一下吗？

我将如何处理递归方法？

public int  mul(int lhs, int rhs)
{
    if (rhs == 0 || lhs == 0) return 0;
    else if(rhs == 1) return lhs;
    return add(lhs, mul(lhs, dec(rhs)));
}

除非有人要求其他人，否则我将仅保留 1 个递归示例。if 和 else if 分别被认为是常数时间，对吗？然后返回调用各种其他递归方法，以及它本身（显然），我真的不知道从哪里开始。

有人可以尝试简单地解释一下吗？

编辑：添加战俘

public int pow(int lhs, int rhs)
{
    int ans = lhs;
    for(int i = rhs; i > 1; i--)
    {
    ans = mul(ans,lhs);
    }
    return ans;
}
4

2 回答 2

1

Big-Oh 背后的想法是它是特定算法的平均运行时间。在分析运行时，您正在寻找关键的东西，例如：

  • 正在使用的参数与正在使用它进行的操作的关系
  • 代码的“关键部分”与传入的参数的关系

您还需要寻找其他一些东西，例如最佳和最坏情况的行为。

现在，谈谈你的方法。

  • 两者inc和dec都是恒定的时间。它们不再需要根据传入参数的大小来执行。

  • add绑定到 的大小rhs，因为您为 中的每个值递增一步rhs。所以那个运行时间是 O(n).*

  • mul，根据您的递归示例，具有三种情况：两个基本情况和一个迭代情况。假设基本案例在恒定时间内运行，但由于存在迭代案例，它超过了基本案例的运行时间。

    在这种情况下，您会受到rhs传入大小的限制，因此它将在 O(n) 时间内运行。

  • fac绑定到num传入的大小。它将是 O(n) 运行时。

  • div绑定到lhs，它将在 O(n) 运行时。

*：说说两个数字相加的一种奇怪方法……

于 2013-04-15T00:19:40.540 回答
0

inc并且dec是 O(1)，因为它们总是可以在恒定数量的操作中完成，并且它们不依赖于您作为参数传递的值。

add，例如，取决于您作为参数传递的数字，所以如果我们认为这个数字是我们的“订单”，add则为 O(n)。

简单地说：作为参数传递的值越高，需要执行的操作就越多。由于这种增加是线性的（粗略地说，如果增加 100，您将增加相同数量级的操作）。

您的mul实现也将在 O(n) 时间内运行，因为这是您拥有的更“昂贵”操作的成本，add.

您需要了解的是 Big-O 表示法的含义：算法运行时间与输入大小变化之间的关系。

如果您牢记这一点，您将更容易计算出方法的成本。

于 2013-04-15T00:20:29.980 回答