算法基础知识

cnbigmx 萌新
  2023-10-26 19:21:08 2023-10-26 19:21:08 创建   2023-10-26 19:34:55 2023-10-26 19:34:55 更新    445 字  1 分钟  

算法

对特定问题求解步骤的描述，具有有穷性、确定性、可行性、输入性、输出性。

时间复杂度

时间复杂度是指算法中的所有语句的频度（执行次数）之和，记为：T(n)=O(f(n)) ,其中n是问题的规模，f(n)是问题规模n的某个函数，忽略高阶项常数系数和低阶项。

ᵏⁿ

示例一：

1
2
int sum =0;
sum=n*(n+1)/2;

时间复杂度为

示例二：

1
2
3
int x=2;
while(x<n/2)
  x=2*x;

设执行频率最高的语句共执行了次，则故所以

示例三：

1
2
3
4
5
6
int i,j;
for(i=0;i<n;i++)
{
    for(j=0;j<m;j++)
        sum+=1;
}

若则

示例四：

1
2
3
4
5
6
int i,j;
for(i=0;i<n;i++)
{
    for(j=0;j<m;j++)
        sum+=1;
}

取最大值

空间复杂度

空间复杂度S(n)是指在算法运行过程中所使用的辅助空间的大小。记为：S(n)=O(f(n))

空间复杂度 O(1)

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

1
2
3
4
5
int i = 1;
int j = 2;
++i;
j++;
int m = i + j;

代码中的 i、j、m 所分配的空间都不随着处理数据量变化，因此它的空间复杂度 S(n) = O(1)

空间复杂度 O(n)

1
2
3
4
5
6
int[] m = new int[n]
for(i=1; i<=n; ++i)
{
   j = i;
   j++;
}

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

此页目录
算法基础知识
  1. 算法
    1. 时间复杂度
      1. 示例一：
      2. 示例二：
      3. 示例三：
      4. 示例四：
    2. 空间复杂度
      1. 空间复杂度 O(1)
      2. 空间复杂度 O(n)