leetcode

leetcode

拓展延伸

算法

算法设计的要求

1. 正确性

   算法满足问题要求，能正确解决问题，算法转化为程序后要注意：

   • 程序中不含语法错误
   • 程序对于几组输入数据能够得出满足要求的结果
   • 程序对于精心选择的、典型的、苛刻且带有刁难性的几组输入数据能够得出满足要求的结果
   • 程序对于一切合法的输入数据都能得出满足要求的结果

   通常以第三层意义上的正确性作为衡量一个算法是否合格的标准

2. 可读性

   算法主要是为了人的阅读和交流，其次才是为计算机执行，因此算法应该是易于人的理解

   另一方面，晦涩难读的算法易于隐藏较多错误而难以调试

3. 健壮性

   指当输入非法数据时，算法恰当的做出反应或进行相应处理，而不是产生莫名其妙的输出结果

   处理出错的方法，不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理

4. 高效性

   要求花费尽量少的时间和尽量低的存储需求

算法和算法分析

一个好的算法首先要具备正确性，然后是健壮性，可读性，在几个方面都满足的情况下，主要考虑算法的效率，通过算法的效率高低来判断不同算法的优劣程度

算法效率以下两个方面来考虑

1. 时间效率：指的是算法所耗费的时间
2. 空间效率：指的是算法执行过程中所耗费的存储空间

时间复杂度T(n)按数量级递增顺序为：

常数阶O(1) --> 对数阶O(lgn) --> 线性阶O(n) --> 线性对数阶O(nlgn) --> 平方阶O(n*n) --> 立方阶O(n*n*n) --> K次方阶O(n的k次方) --> 指数阶O(2的n次方)

空间复杂度：算法所需存储空间的度量 S(n) = O(f(n))

需要考虑的是算法本身要占据的空间，输入/输出，指令，常数，变量等以及算法要使用的辅助空间

结合代码更容易理解

// 将一维数组a中的n个数逆序存放到原数组中
// 第一种算法
for(let i = 0;i < n /2; i ++) {
  t = a[i]
  a[i] = a[n - i - 1]
  a[n - i - 1] = t
}

// 第二种算法
for(let i = 0; i < n; i ++) {
  b[i] = a[n - i - 1]
}

for(let i = 0; i < n; i ++) {
  a[i] = b[i]
}

第一种算法呢只需要提供一个辅助变量空间即可，所以空间复杂度是常数阶的 O(1)

第二种算法中a有多少，那么b就需要提供相同长度的空间，所以空间复杂度是O(n)