时间复杂度与空间复杂度

1.时间复杂度

时间复杂度是评估程序算法效率的数学工具

$O(1),O(\sqrt{n}),O(log n),O(n),O(nlogn),O(n^2),O(n^3),O(2^n),O(n!)$

在计算时间复杂度的时候，去掉最高次项并且只保留要系数。

列如：$3n^3+2n^2+10n+5$ 那么该程序的时间复杂度就是 $O(n^3)$

1. $O(1)$ 常量阶

若程序存在的变量不会影响程序执行次数，这样的程序的时间复杂度就是 $O(1)$

int fun(int n){		//计算1-n的和
  int s=(1+n)*n/2;
  return s;
}

2. $O(\sqrt{n})$ 根号阶

int fun(int n){
  for(int i=2;i*i<=n;i++)
    if(n%i==0)
      return 0;
  return 1;
}

3. $O(logn)$ 对数阶

4. $O(n)$ 线性阶

int fun(int n){		//计算1-n的和
  int s=0;
  for(int i=1;i<=n;i++)
      s+=i;
  return s;
}

5. $O(nlong)$ 线性对数阶

6. $O(n^2)$ 平方阶

int fun(int a[][],int n){	//统计二维的数组中数字1的个数
  int s=0;
  for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
      if(a[i][j]==1)
        s++;
  return s;
}

7. $O(n^3)$ 立方阶

int fun(int n){
  for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
      for(int k=1;k<=n;k++)
        cout<<i<<j<<k;
}

8. $O(2^n)$ 指数阶

9. $O(n!)$ 阶乘阶

时间复杂度	能解决的数据范围
$O(1)/O(\sqrt{n})/O(logn)$	非常大
$O(n)$	$10^7-10^8$
$O(logn)$	$10^5-10^6$
$O(\sqrt{n})$	$10^5$
$O(n^2)$	$5000-10000$
$O(n^3)$	$100-300$
$O(2^n)$	$25$
$O(n!)$	$10$

二.空间复杂度

$O(1)/O(n)/O(n^2)$

$O(1)$ 没有用数组或递归

int fun(int n){
  int s=0;
  for(int i=1;i<=n;i++)
        s+=i;
  return s;
}

$O(n)$ 线性阶

int fun(int a[],int n){
  int s=0;
  for(int i=1;i<=n;i++)
    s+=a[i];
  return s;
}

$O(n^2)$

int fun(a[][],int n){
  int s=0;
  for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
      if(a[i][j]==8)
        s++;
  return s;
}

有部分省略

后面会补