算法

[conan1992]

算法

算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或者多个操作

5个基本特征

输入、输出、有穷性、可行性、确定性

• 输入
  算法具有0个或者多个输入
• 输出
  • 至少有一个或者多个输出
  • 输出的形式可以是打印形式输出，也可以返回一个值或者多个值等

function print(){
console.log("hello")
}

• 有穷性
  指算法在执行有限的步骤后，自动结束而不会出现无限循环，并且每一个步骤在可接受的时间内完成。
• 确定性
  • 算法的每一个步骤都具有确定的意义，不会出现不确定性。
  • 算法在一定条件下，只有一条执行路径，相同的输入只能有唯一的输出结果
  • 算法的每个步骤都要改被精确定义而无歧义。
• 可行性
  • 算法的每一步都必须是可行的，也就是说，每一步都能够通过执行有限次数完成

算法设计要求

• 正确性
  • 算法的正确性是指算法至少应该具有输入、输出、和加工处理无歧义性、能正确反映问题的需求，能够得到问题的正确答案
  • 四个方面
    算法程序没有语法错误；
    算法程序对于合法输入能够产生满足要求的输出；
    对于非法输入能够产生满足规格的说明；
    对于故意刁难的测试输入有满足要求的输出结果；
• 可读性
  • 算法设计的另一个目的是为了便于阅读、理解和交流；
• 健壮性
  当输入数据不合法时，能做出相关处理，而不是产生异常、奔溃或者其他问题；
• 时间效率高和存储量低

时间复杂度

算法时间复杂度：在进行算法分析是，语句总的执行次数T（n）是关于问题规模n的函数，进而分析T(n)随n的变化情况并确定T（n）的数量级。

算法的时间复杂度，也就是算法的时间量度，记做：
T(n) = O(f(n)).
它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐进时间复杂度，简称为时间复杂度，其中f(n)是问题规模n的某个函数
注：需要知道的事执行次数==时间

• 这样用大写O（）来体现算法时间复杂度的记法，我们称之为大O阶记法；例如O（1），O（n），O（n^2）

• 如何推导大O阶方法

  • 用常数1取代运行实践中的所有加法常数
  • 在修改后的运行次数函数中，只保留最高阶项
  • 如果最高阶项存在且不是1，则去除与这个项相乘的常数
  • 得到的最后结果就是打O阶

• 类型

  • 常数阶O(1);
  • 线性阶O(n);
  • 平方阶O(n^2);
  • 对数阶O(log(2)n)

var i,j,n = 100;
for(i=0;i<n;i++){
  for(j=i;j<n;j++){
   console.log("hello world\n")
}
}
/* n+(n-1) + (n-1) +...+1 = n(n+1)/2 = n^2 + n/2
=> 用推导大O攻略，第一条忽略，因为没有常数相加，第二条只保留最高项，所以n/2去掉；最后第三条去除与最高项相乘的常数，最后得出O(n^2) */

var i=1,n=100;
while( i<n){
i = i*2
}
/*
=> 假设有x个2相乘后大于或等于n，则退出循环；
=> 2^x=n => x = log(2)n所以这个循环之间复杂度为O(logn)
*/