数据结构与算法(一) 简单例子理解时间复杂度和空间复杂度

public static void test(int n) {
  // i = 0 执行1次  i < n 执行n次 i++ 执行n次
  for (int i = 0; i < n; i++) {
      // j = 0 执行n次  j < n 执行n^2次 j++ 执行n^2次
    for (int j = 0; j < n; j++) {
      //执行n^2次
      System.out.println("123");
    }
  }
}

public static void test2(int n) {
 // i = 0 执行1次  i < n 执行n次 i++ 执行n次
  for (int i = 0; i < n; i++) {
    //j = 0 执行n次   j < i 执行 0 + 1 + 2 + 3 +...+ (i - 1)次  j++执行 0 + 1 + 2 + 3 +...+ (i - 1)次
    for (int j = 0; j < i; j++) {
      //执行 0 + 1 + 2 + 3 +...+ (i - 1)次
      System.out.println("123");
    }
  }
}

public static void test3(int n) {
   // i = 0 执行1次  i < n 执行n次 i++ 执行n次
  for (int i = 0; i < n; i++) {
    //j = 0 执行n次
		// j + = j等价于 j = j * 2  所以执行次数就是 2^j < n 因为2^j = n  j = log2^n
    // 因为log5^n = log2^5 *long5^n  所以一般我们忽略底部系数 次数为log n
    // 所以j < n 和 j += j 的执行次数为n * logn
    for (int j = 0; j < n; j += j) {
      // 执行次数为n * logn
      System.out.println("123");
    }
  }
}

	public static int fib(int n) {
		if(n <= 1 ) return n;
		return fib(n - 1) + fib(n - 2);
	}

public static int fib2(int n) {
  if (n <= 1) {
    return n;
  }
  // 1
  int first = 0;
  // 1
  int second = 1;
  // int i > 1次  i的判断 -> n-1次  i++ -> n-1次
  for (int i = 0; i < n - 1; i++) {
    int  sum = first + second;
    first = second;
    second = sum;
  }
  return second;
}