1

首先，这是我的 O(n) 代码：

import java.util.*;

public class BigO{

  public static void main(String[] args)
  {
    Scanner in = new Scanner(System.in);
    System.out.print("Enter a number: ");
    String userInput = in.nextLine();
    int mNum = Integer.parseInt(userInput);

    int y = new BigO().linear(mNum);
    System.out.println(y);
  }

 //O(n) - Linear
 public int linear(int n) {
  int sum = 0;
  for (int j = 0; j < n; j++) {
   sum++;
   System.out.print(sum + " ");
  }
  return sum;
 }

如果这是一个愚蠢的问题，我深表歉意，因为我已经很长时间没有使用大 O 表示法了，我想确定一下，但是对于我上面的任何内容，它是自下而上还是自上而下的计算？如果两者都不是，我该如何处理其中一个（或两者）？请告诉我。谢谢。

更新： 好吧，没关系，我问了我班上的一些朋友以及教授，他错误地写下了我们的问题。他纠正了它，意思是说我们应该对递归斐波那契使用这种类型的 O(n) 时间算法。对不起，哈哈。

4

1 回答 1

5

大 O 与自上而下/自下而上无关。

  • 第一个是指一种表示算法复杂性和运行时间的方法，具体取决于其输入的大小。
  • 第二个是指将问题分解为子问题以达到解决方案时所采取的方法。

所有这些都可以通过谷歌搜索访问:)。

于 2012-08-24T20:32:03.357 回答