盒子
盒子
文章目录
  1. 名字解释

算法和数据结构是什么

程序=算法+数据结构

这是一句非常著名的话,凭借这一句话直接获得图灵奖,可想数据结构和算法有多重要。同时,在各个大厂招聘面试时,也会提到数据结构和算法。

你知道什么什么数据结构吗

查找、插入等操作的时间复杂度是多少

给出一个问题,问需要用到什么数据结构,时间和空间的复杂度分别是什么,可不可以优化。

所以一名优秀的程序员,应该了解和使用数据结构和算法。

那么什么是数据结构,算法又是什么呢。

名字解释

我的大学老师这样解释数据结构和算法:

数据结构是对所有数据的元素和元素与元素关系的描述,算法是对特定问题求解步骤的描述

数据是描述客观事物的数和字符的集合,在计算机的角度,所有能输入到计算机中且能被计算机处理的符号都是数据。

数据项是具有独立含义的数据最小单位。

数据结构是以某种关系将数据联系在一起,而算法是对特定问题求解步骤的一种描述,是指定的有限序列。

在实现算法中需要使用到数据结构来减少步骤,提高效率。

一般来说,判定一个算法的好坏,有两方面的标准,一个是代码运行的时间,另一个是代码运行占用的空间,分别称为时间复杂度空间复杂度

我们一般用O来表示时间复杂度,如下代码:

1
2
3
4
for( i=1; i<=n; i++) {
j = i;
j++
}

这段代码会从i=1执行到i=n,代码执行了n次。代码的执行次数与n的大小有关,所以用O(n)来表示这段代码的时间复杂度。

常见的时间复杂度由小到大依次为:

  • O(1)
  • O(log~2~N)
  • O(n)
  • O(nlog~2~N)
  • O(n²)
  • O(n³)
  • O(2^n^)

在高中学过的数学就可以证明几种函数的增长趋势,当随着n变大,计算机运行时间也要变长,尤其是指数方式增长,运行时间将漫长无比。在计算机中, 为了降低时间复杂度,有多种方法,一种是空间换取时间,如桶排序等;或者是优化算法,降低时间复杂度。

显然,时间复杂度只是一种增长趋势,而不是具体的使用了多少时间,空间复杂度同样不是计算程序具体使用了多少空间,而是指一个算法在运行中,使用了多少临时空间的一个度量

例如,如果在算法中定义了一个变量,那么空间复杂度就是常数级,也就是O(1)。如果定义了一个长度为n的数组,那么空间复杂度就是O(n)。

现在计算机的性能越来越好,空间资源可以说是足够多,所以算法优化主要是对时间复杂度的优化,甚至会用空间换取时间。

所以,知道了什么是数据结构和算法,接下来的文章开始学习数据结构和算法,一起向一名优秀的打工人进步吧。

欢迎关注公众号
扫码关注我的微信公众号-大前端合集
  • 微信公众号-大前端合集