数据结构与算法之基础概念

前言：

算法是一个程序员必备的内力，国外的大厂面试90%的题都是考算法，他们是非常重视算法基础的，他们认为任何一门编程语言花不了多长时间就能上手，所以他们最主要的就是考验程序员的内力（算法基础、逻辑基础、数学基础）。国内的BATJ也非常重视算法基础，如果你想进大厂，那么你必学算法。

什么是数据结构？

Data Structure，存储数据的不同方式。

比如说，有10个int型的整数，你可以每个整数一个小格，并排的挨在一起，这种叫数组；你也可以每个小格除了存自己之外还存指向下一个小格的指针，这种数据结构叫链表。所以你看到，数据有很多种存储方式，对于不同的问题我们采取不同的存储方式，这种我们叫数据结构。

什么是算法？

Algorithm，同一个问题不同的解决方法。

比如说，要计算1 + 2 + 3 + … + 99 = ? 第一种算法你可以从前往后一直加；第二种你可以首尾相加；这种叫算法。

如何计算算法的优劣？

时间维度

完成同一件事，用时最少，算法越好。

时间复杂度

时间复杂度用O表示，随着数据的规模不断扩大，时间变化的规律。讲一个算法的时间复杂度，一般讲的都是最差的情况。

比如O(1)表示花费时间最短，不管数据规模如何扩大，时间不随数据的增加而改变。

O(n)表示随着数据规模的增加，花费的时间也会随数据的增加而线性的扩大。

思考题：求以下问题的时间复杂度

• 查找数组最后一个位置上的数

  数组的长度是固定的，当我查某一位置的值的时候，我通过计算长度就能锁定目标位置，所以不管数据如何增加，时间复杂度就是O(1)

• 查找链表最后一个位置上的数

  要想查链表上的值，我得从第一个位置开始遍历，直到最后一个，随着数据量的增加，遍历的次数也随之增加，所以时间复杂度是O(n)

• 对数组求和

• 查找数组的最大值

空间维度

完成同一件事，占用额外的空间越小，算法越好。