数据结构与算法分析——开篇以及复杂度分析

开篇

你也许已经发现了,工作了几年,原以为已经是一只老鸟。但看到刚参加工作的同事,你发现,原来自己一直在原地踏步。跟新人相比,你的唯一优势就是对业务更熟悉而已,别的就没有什么优势了。

怎样才能够让自己更上一层楼呢?学习更多的框架?做更多项目?其实,程序员真正要做的是修炼内功,也就是夯实基础。比如设计模式、网络原理,当然也包括接下来要说的数据结构与算法分析。

一、为什么要学习数据结构与算法分析

  1. 告别烂代码,写出性能更好地代码。
  2. 解决问题的思路和方法,编程之外也有应用。
  3. 思考能力才是程序员的核心竞争力,而算法能够有效地锻炼这方面。

当然也有其他原因,进大厂、不被淘汰、完成领导对代码简洁度性能的要求。

二、如何学好

  1. 边学边练,一周用 2~3 个小时刷题。
  2. 带着疑问去学习,多想为什么。
  3. 学习算法是个需要沉淀的过程,切勿急于求成。

三、复杂度分析

复杂度分析是算法学习的精髓,几乎贯穿整个学习过程。掌握了复杂度分析,恭喜你,数据结构与算法分析的学习已经完成了一半。

  • 时间复杂度

大 O 时间复杂度实际并不是代码的真正执行时间,而是代码执行时间随数据规模增长而呈现的变化趋势。程序真正执行时间受环境以及数据规模影响很大,例如相同条件下 i7 处理速度肯定比 i5 快,i7 处理器处理 10 条数据肯定比 10W 条块。
常见的空间复杂度就是 常量阶 O (1)、线性阶 O (n)、指数阶、对数阶 O (logn)、线性对数阶 O (nlogn),指数阶。

funtion sum (int n) {   
    int sum = 0;    
    for (int i=1; i <= n; i++) {    
        sum = sum + i;  
    }   
    return sum; 
}
# 第 2 行代码执行了一次,第 3 、4各执行了 n 遍。所以时间复杂度为 2n + 1 , 也就是 n 。
  1. 最好时间复杂度
  2. 最坏时间复杂度
  3. 均摊时间复杂度

    funtion find ( int[] array ,  int n ,  int m ) { 
    int position = -1;  
    for (; i < n; ++i) { 
        if (array[i] == m) {       
            position = i;       
            break;  
        }  
    }
    return position;
    }
    #如上代码,寻找m在数组中的位置。如果第一个元素就是 m 时间复杂度就是 1 。如果 m 不在数组中,时间复杂度就是 n 。这是就用到最好时间复杂度、最坏时间复杂度和平均时间复杂度。
    #最好情况,第一个元素就是m。所以,最好时间复杂度就是 1 。
    #最坏情况,m 不在数组中。所以,最好时间复杂度就是 n 。
    #均摊时间复杂度,此时共有 n + 1 可能性。每种情况累加后再除 n + 1,就是均摊时间复杂度。( 1 + 2 + 3 ..... n + n ) / ( n + 1 ) = n ( n + 3 ) / 2 ( n + 1 ) ,简化后就是 n 。
    
  • 空间复杂度

空间复杂度表示的是存储空间与数据规模之间的增长关系。

funtion getArray ( int n) {
    int i = 0;  
    int[] a = new int[n];
    for (  ; i <n; ++i) {  
        a[i] = i;  
    }
    return a;
}
#第 2 行代码申请了变量 a ,别处就没有再申请存储了。所以,空间复杂度就是 n 。

今日笔记主要内容是时间复杂度,只列举了简单的例子。

网上有很多题,建议大家去做下,熟能生巧是很有道理的。

以上内容,如有错误点或改进点,希望大家能够指出。有什么问题,也可以留言,大家一起讨论、学习,一起进步。

Image placeholder
oi-io
未设置
  0人点赞

没有讨论,发表一下自己的看法吧

推荐文章
数据结构与算法分析——开篇以及复杂度分析

开篇你也许已经发现了,工作了几年,原以为已经是一只老鸟。但看到刚参加工作的同事,你发现,原来自己一直在原地踏步。跟新人相比,你的唯一优势就是对业务更熟悉而已,别的就没有什么优势了。怎样才能够让自己更上

数据结构与算法分析——链表

链表链表是一种常见的数据结构,是一组有序的数据,每个链表中的数据项称为元素。它跟数组很像,二者对比学习会更容易理解和记忆。数组是内存中连续的一块,不会间断。链表在内存中不一定是连续的一块。如果内存只剩

数据结构与算法分析——队列

定义队列,和栈类似,也是一种操作受限的线性表数据结构。与栈结构不同的是,可以对队列2端操作,要求数据从一端进(入队),从另一端出(出队)。队列遵循"先进先出"的原则,即最先进队列的数据元素,同样要最先

数据结构与算法分析——栈

定义栈是一种操作受限的线性表,只支持在一端进行插入和删除操作(入栈和出栈)。后进先出、先进后出是它最大的特点。当某个数据集合只在一端插入和删除数据,并满足先进后出的特性时,就可以选择栈这种数据结构。实

JavaScript 的数据结构和算法

现在有个还不是好的项目,未来会成为好的项目的项目想介绍给大家。传送门https://github.com/MasterShu/JavaScript-Da...这个是本人在维护的一个项目。主要是使用Ja

Pandas数据分析——超好用的Groupby详解

微信公众号:「Python读财」如有问题或建议,请公众号留言在日常的数据分析中,经常需要将数据根据某个(多个)字段划分为不同的群体(group)进行分析,如电商领域将全国的总销售额根据省份进行划分,分

【数据结构】2_数据的艺术

程序设计的挑战 利用计算机解决现实生活中的问题 生活中的不同个体之间存在联系 用计算机程序描述生活中个体间的联系 问题:如何描述生活中的个体?数据的概念程序的操作对象,用于描述客观事物数据的特点 可以

TensorFlow 2.0 代码实战专栏开篇

作者|  AymericDamien编辑 | 奇予纪出品| 磐创AI团队原项目|  https://github.com/aymericdamien/TensorFlow-Examples/ 写在前面

kernel的结构与命令行参数

kernel包结构在RHEL中rpm包是一种cpio格式的压缩文件,它由源文件和元数据(metadata)组成。而在rpm包中kernelrpm比较特殊,是一个只有元数据的包,在元数据中约束了以下的包

python set (集合)数据结构

set(集合)是一个非常有用的数据结构。它与列表(list)的行为类似,区别在于set不能包含重复的值。这在很多情况下非常有用。例如你可能想检查列表中是否包含重复的元素,你有两个选择,第一个需要使用f

Python入门教程_5. 数据结构

这个章节将更详细地描述一些你已经了解的内容,并且添加了一些新的内容。 5.1.深入列表对象 List数据类型包含更多的方法,下面是List对象包含的所有方法: list.append(*x*) 将一个

【数据结构】3_程序设计的灵魂

学员间的对话 木暮:我发现三井真是牛,只用一行就实现了strlen 宫城:那么强!他是怎么做的呢? 木暮:不知道,我看了一下,没看懂。。。 宫城:牛人就是牛人啊! 问题:程序是否越短越好?是否别人看不

【数据结构】1_进阶高手的大门

理解程序的本质问题:为什么会有各种各样的程序存在?程序的本质是什么?程序是为了解决实际问题而存在的,从本质而言,程序是解决问题的步骤描述。一小步的进阶:理解实际问题 确认问题类型 如:数值计算,求最

java与数据结构

数组与链表数组 数组是数据结构中的基本模块之一 数组是一种基本的数据结构,用于按顺序存储元素的集合。但是元素可以随机存取,因为数组中的每个元素都可以通过数组索引来识别。 数组可以有一个或多个维度

redis数据结构(二) - 字符串

基于redis5.0的版本。字符串编码:字符串对象的编码可以是int,raw或者embstr。1.rawraw就是redisObject+sds,即redisObject的ptr指针指向一个sds对象

Redis的数据结构和内部编码

redis是单线程,一次只执行一条命令,那为什么可以这么快: 纯内存 非阻塞IO 避免线程切换和竞态消耗 在使用过程中要注意: 一次只运行一条命令 避免长(慢)命令,例如keys、flushall、f

【数据结构】 10_C++异常简介

C++内置了异常处理的语法元素try...catch... try语句处理正常代码逻辑 catch语句处理异常代码逻辑 try语句中的异常由对应的catch语句处理 try { doubler=

第一章:数据结构绪论

[[数据结构-第1章]绪论目录 [1数据结构有什么用?] [2基本概念和术语] [3逻辑结构与存储结构] [3.1逻辑结构] [3.2存储结构] [4抽象数据类型] [4.1数据类型] [

【数据结构】11_异常类构建

异常的类型可以是自定义类类型 对于类类型异常的匹配依旧是至上而下严格匹配 赋值兼容性原则在异常匹配中依然适用 一般而言 匹配子类异常的catch放在上部 匹配父类异常的catch放下下部 现代

爱奇艺RND框架技术探索——架构与实现

前言RND,全称ReactNodeDesktop,起源于RN在爱奇艺PC端的实现,采用ReactJSframework+Node.jsruntime+nativeUIengine架构,目标是成为最轻量

使用Jupyter NoteBook进行IB查询和交易,以及使用算法交易示例

在搞好IB盈透接口后,试了下客户端交易,但是最终目的还是使用程序化交易。发现vnpy已经提供的Script_engine来支持JupyterNoteBook交易的,而且非常方便调用。 这里就用写了基于

包银消费CTO汤向军:消费金融大数据风控架构与实践

01风险在哪里1.1 信用风险根据银行业的风险理论,信用风险是指借款人因各种原因未能及时、足额偿还债权人或银行贷款而违约的可能性。信用风险的风控重点在于,甄别客户违约的原因究竟是还款能力,还是还款意愿

Laravel 第八章学习——中间件以及策略

中间件 Laravel中间件(Middleware)为我们提供了一种非常棒的过滤机制来过滤进入应用的HTTP请求,例如,当我们使用Auth中间件来验证用户的身份时,如果用户未通过身份验证,则Auth中

Laravel 第八章学习——中间件以及策略

中间件Laravel中间件(Middleware) 为我们提供了一种非常棒的过滤机制来过滤进入应用的HTTP请求,例如,当我们使用Auth中间件来验证用户的身份时,如果用户未通过身份验证,则Auth中

亿级海量数据的实时读写和复杂查询实践

摘要:本文分享了每日亿级增量数据的实时读写、复杂查询场景实践介绍,涉及MySQL分表分库策略、数据异构、TiDB使用和优化、微服务架构等内容。  作者:黄哲铿  黄哲铿,中通商业CTO,前1号店技术总