时间复杂度&空间复杂度

Contents

1. 1. 0.时间复杂度与空间复杂度
   1. 1.1. 1.时间复杂度
      1. 1.1.1. 常见的时间复杂度量级
         1. 1.1.1.1. a.常数阶O(1)
         2. 1.1.1.2. b.线性阶O(n)
         3. 1.1.1.3. c.对数阶O(logN)
         4. 1.1.1.4. d.线性对数阶(nlogN)
         5. 1.1.1.5. e.平方阶(n²)
         6. 1.1.1.6. f.立方阶O(n³)、K次方阶O(n^k)
   2. 1.2. 2.空间复杂度
      1. 1.2.1. 常见的空间复杂度量级
         1. 1.2.1.1. a. O(1)
         2. 1.2.1.2. b. O(n)

0.时间复杂度与空间复杂度

我们衡量算法的优劣主要通过两个维度时间``空间,而这两个维度对应的就是时间复杂度``空间复杂度.
但鱼和熊掌不可兼得,我们只能在这两者间取得一个合适的平衡点

1.时间复杂度

算法所需要的时间工作量

• 标记公式
  • T(n) = O(n)

常见的时间复杂度量级

a.常数阶O(1)

int i = 1;
int j = 2;
++i;
j++;
int m = i + j;

b.线性阶O(n)

for(i=1; i<=n; ++i)
{
   j = i;
   j++;
}

c.对数阶O(logN)

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

d.线性对数阶(nlogN)

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

e.平方阶(n²)

for(x=1; i<=n; x++)
{
   for(i=1; i<=n; i++)
    {
       j = i;
       j++;
    }
}

如果把一层循环的n改成m,时间复杂度就成了 O(m*n)

for(x=1; i<=m; x++)
{
   for(i=1; i<=n; i++)
    {
       j = i;
       j++;
    }
}

f.立方阶O(n³)、K次方阶O(n^k)

参考的O(n²),O(n³)相当于三层n循环

2.空间复杂度

算法在运算中临时占用的控件的大小

• 标记公式
  • S(n) = O(n)

常见的空间复杂度量级

a. O(1)

如果算法执行所需要的临时空间不随着某个变量n的大小而变化，即此算法空间复杂度为一个常量，可表示为 O(1)

int i = 1;
int j = 2;
++i;
j++;
int m = i + j;

b. O(n)

int[] m = new int[n]
for(i=1; i<=n; ++i)
{
   j = i;
   j++;
}

这段代码中，第一行new了一个数组出来，这个数据占用的大小为n，这段代码的2-6行，虽然有循环，但没有再分配新的空间，因此，这段代码的空间复杂度主要看第一行即可，即 S(n) = O(n)