专栏首页M不作声什么是数据结构和算法

什么是数据结构和算法

❝程序=算法+数据结构 ❞

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

❝你知道什么什么数据结构吗 查找、插入等操作的时间复杂度是多少 给出一个问题,问需要用到什么数据结构,时间和空间的复杂度分别是什么,可不可以优化。 ❞

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

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

名字解释

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

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

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

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

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

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

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

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

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

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

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

  • O(1)
  • O(logN)
  • O(n)
  • O(nlogN)
  • O(n²)
  • O(n³)
  • O(2^n^)

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

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

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

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

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

本文分享自微信公众号 - 大前端合集(fe-stack),作者:M不作声

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-11-09

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 反转单链表

    这结果简直拉胯,我们来做时间和空间复杂度分析,将链表遍历一遍拆掉入栈,然后再将栈遍历一遍出栈生成链表,时间复杂度大致为O(2n),而为了存储节点借用了一个栈的数...

    不作声
  • CSP

    该评论被提交后,会存储在数据库中,当其他用户打开该页面时,该代码会被自动执行,用户就会被攻击到。

    不作声
  • 从minipack看打包原理

    minipack是一个小型的打包工具,作者ronami,用来解析打包工具的基本原理。代码中有相当多的注释,理解起来也非常容易。

    不作声
  • 如何学好数据结构和算法

    数据结构和算法是计算机科学中最重要的课程,作为一名Google的软件工程师,我经常看到一些求职者或刚毕业的学生,他们对于数据结构和算法的学习是远远不够的。这不是...

    wangxl
  • 「时间」与「空间」复杂度

    算法(Algorithm)是指用来操作数据、解决程序问题的一组方法。对于同一个问题,使用不同的算法,也许最终得到的结果是一样的,比如排序就有前面的十大经典排序和...

    小小詹同学
  • 数据结构01 算法的时间复杂度和空间复杂度

    1、算法的概念: 算法 (Algorithm),是对特定问题求解步骤的一种描述。 解决一个问题往往有不止一种方法,算法也是如此。那么解决特定问题的多个算法之间如...

    nnngu
  • 冰与火之歌:「时间」与「空间」复杂度

    算法(Algorithm)是指用来操作数据、解决程序问题的一组方法。对于同一个问题,使用不同的算法,也许最终得到的结果是一样的,比如排序就有前面的十大经典排序和...

    五分钟学算法
  • Zookeeper搭载kafka消息发布和订阅

    ZooKeeper 是一个开源的分布式协调服务,由雅虎创建,是 Google Chubby 的开源实现。

    刘文正
  • 对比Spring IoC两种开发方式:XML和注解

    今天楠哥给大家讲讲在实际开发中经常会使用到的 IoC 技术:通过 IoC 容器架构程序的分层实现,有两种方式:基于 XML 配置文件和基于注解。

    南风
  • MySQL存储过程举例

    存储过程可能是很多人都比较喜欢使用的,但MySQL不建议使用存储过程,如果临时用的话可以考虑。

    July

扫码关注云+社区

领取腾讯云代金券