算法简介

算法简介

算法是指令的集合，为了解决特定问题而规定的一系列操作，具有五个特征

• 有穷性 一个算法在经过有限的步骤后必然停止
• 确定性 一个算法的每一个步骤必须精确地定义，要执行的每一步必须都没有歧义
• 输入 一个算法有零个或多个输入
• 输出 一个算法有一个或多个输出
• 可行性 算法的每一步都必须是可行的

算法性能分析

在计算及资源中，最重要的就是时间和空间，所以评价一个算法的好坏，使用对资源占用的时间和空间的好坏，也就分为了时间复杂度和空间复杂度

时间复杂度

对于一个算法来评判时间复杂度，其并不是简单地来计算运行时间为n秒，这是没有意义的，所以在进行分析时是假设一些基本操作都是可以在一个常数时间内完成的，而算法执行基本操作的次数可以反映算法的运行时间

而且在评估算法时也不需要精确地进行计算，可以去除掉一部分低阶项和首项常数，就衍生出了使用大O表示法来表示时间复杂度

那怎么来推导大O阶呢

• 用常数1取代运行时间中的所有加法常数
• 修改后的运行次数函数中，只保留最高阶项
• 如果最高阶项存在且不是1，则去除与该项相乘的常数

来看几个示例

常数阶

O(1)称为常数阶

int sum=0,n=100; // 执行一次
sum = (1+n)*n/2; // 执行一次

该函数就是f(n)=2，根据上述进行推导

• 把常数项2改为1
• 修改之后保留最高阶，该函数没有最高阶，所以时间复杂度为O(1)

线性阶

O(n)称为线性阶

int[] fs = new int[n]; // 执行一次
fs[0] = 1;// 执行一次
fs[1] = 1;// 执行一次
for (int i = 2; i < n; i++) {
  fs[i] = fs[i - 1] + fs[i - 2]; // 执行n-2次
}

该函数就是f(n)=n+1，根据上述进行推导

• 把常数项为1
• 修改之后只保留最高阶，为n，最后得到O(n)

对数阶

O(logn)称为对数阶

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

这里可以通过$2^x = n$得到 $x= log_{2}n$，也就是时间复杂度为O(logn)

平方阶

$O(n^2)$称为平方阶

int i,j;
for(i = 0;i<n;i++){
  for(j=0;j<n;j++){
    
  }
}

空间复杂度

与时间复杂度相对应的，使用空间复杂度来评判算法运行所占用的空间