时间 / 空间复杂度

Ame 收录于

2023-02-25 约 627 字预计阅读 2 分钟次阅读

时间复杂度 & 空间复杂度

1
2


n := 1000
fmt.Println(n)

时间复杂度 O(logn) —对数阶，当数据增大n倍时，耗时增大logn倍（这里的log是以2为底的，比如，当数据增大256倍时，耗时只增大8倍，是比线性还要低的时间复杂度）。二分查找就是O(logn)的算法，每找一次排除一半的可能，256个数据中查找只要找8次就可以找到目标

代码

1
2
3


for i := 1; i < n; i = i * 2 {
  fmt.Println(i)
}

1
2
3


for i := 0; i < n; i++ {
  fmt.Println(i)
}

1
2
3
4
5
6


for i := 0; i < n; i++ {
  fmt.Println(i)
}
for j := 0; j < m; j++ {

} // O(n + m)

线性对数阶O(nlogn)其实非常容易理解，将对数阶O(logn)的代码循环n遍的话，那么它的时间复杂度就是 n * O(logn)，也就是了O(nlogn)，归并排序的复杂度就是O(nlogn)

1
2
3
4
5
6


for (int m = 1; m <= n; m++) {
    int i = 1;
    while (i < n) {
        i = i * 2;
    }
}

1
2
3
4
5
6


for i := 0; i < n; i++ {
  for j := 0; j < n; j++ {
    fmt.Println(i)
    fmt.Println(j)
  }
}

1
2
3
4
5
6


for i := 0; i < n; i++ {
  for j := 0; j < m; j++ {
    fmt.Println(i)
    fmt.Println(j)
  }
}

1
2
3
4
5
6


func fib(n int) int {
  if n <= 0 {
    return 1
  }
  return n * fib(n - 1)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


计算: 1 + 2+ 3 + 4 + 5 + .. + n

方法1: 
y = 0
for i = 1; i <= n; i++ {
  y += i
}

方法2 求和公式:
y = n * (n+1)/2

1
2
3
4
5


func test(n int) []int {
  res := make([]int, 0)
  res = append(res, n)
  return res
}

1

int i;

1

int[] arr;

1

int[][] arr;