Java - Big-O表示法(自下而上或自上而下的方法)

Question

首先,这是我的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)时间算法用于递归的斐波那契.抱歉,哈哈.

Answer 1

Big O与自上而下/自下而上无关.

• 第一种是指表示算法复杂性和运行时间的方式,具体取决于其输入的大小.
• 第二种是指在子问题中解决问题以达成解决方案时采用的方法.

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