【算法】理解算法（一）——算法的时空复杂度_0

写在前面。招聘竞争。笔试和面试是规范求职的坎，而算法是大多数人的难点，只有通过系统的学习和理解才能攻克。为了帮助更多的人理解数据结构和算法，将创建一个新的博文系列《懂点算法》，希望大家能够度过痛苦的日子。本人算法研究能力有限，希望大家提炼精华和干货。什么是算法算法是指用来操作数据和解决程序问题的一组方法。衡量不同算法优劣的方法有两种：后统计法：通过统计和监控，利用计算机定时器比较不同算法的运行时间，以确定算法的效率，但它有很大的局限性。预分析和估计方法：在计算机程序编写之前，根据统计方法对算法进行估计。例如，我们知道斐波那契数列的规则是：数列从第三项开始，每一项的值都是前两项值的和。即：0,1,1,2,3,5,8...解析：我们观察斐波那契数列的规律，我们可以看到，这个数列在用算法表达的时候需要分为两种情况，即计算前两项后的元素，第三项开始。最简单的方法就是用递归来实现斐波那契数列的算法：functionfib(num){if(num<=1)returnnum;returnfib(num-1)+fib(num-2);}当然是也可以使用循环的方式实现：functionfib(num){if(num<=1)returnnum;letnum1=0,num2=1;for(leti=0;i=0;--j){console.log(arr[i]);}}观察上面代码，我们可以得到：在第二行代码中，在内存中开辟一块空间来存放变量arr，并为其赋值一个空数组；第三行代码，设置数组长度为n，数组会自动填充n个undefined；另外剩余的代码并没有占用更多的空间，所以整个代码的空间复杂度为O(n)。最坏情况和平均情况最坏情况运行时间是程序运行时间最长的时间，没有比这更糟的了。通常，当我们提到运行时间时，我们指的是最坏情况下的运行时间。平均运行时间是指程序预期的平均运行时间，但在实际测试中，很难通过分析获得，需要一定的实验数据和估算。我们知道，在n个随机数中寻找一个数时，最好的情况是找到第一个数。此时的时间复杂度是O(1)，最坏的情况是只找到第n个数。那么，求数算法的最坏情况时间复杂度为O(n)，平均情况时间复杂度为O((1+n)/2)或O(n/2)。总结在本文中，作者介绍了什么是算法，为什么要使用算法，如何衡量算法的时间复杂度和空间复杂度，以及算法的最坏情况和平均情况的概念。