数据结构与算法(一)-初识

前言:一个程序员前期可能需要各种业务和编程的能力,但是后期如果想要提高就需要有一个扎实的基础,厚积薄发,所以最近抽空学了下数据结构与算法,颇有感触,学习过程虽然很枯燥,但是坚持了下来,也收获了很多东西,准备总结一下自己得到的知识,一方面防止忘记,另一方面为更深入的知识面打打基础;接下来先介绍一下大概的知识框架

一、数据结构

  对于需要输入大量数据,处理并且输出结果的算法,在输入输出数据或者处理数据的过程中,需要高效的存储和处理各种各样大量的数据。   在某些情况下,正是因为采用了高效的数据存储和管理方式,才使得某些巧妙地算法实现成为可能,而这种大量数据的存储,也就是数据结构了;

百度百科:  
  数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成。记为:
  Data_Structure=(D,R)
  其中D是数据元素的集合,R是该集合中所有元素之间的关系的有限集合。

  数据结构具体指同一类数据元素中,各元素之间的相互关系,包括三个组成部分,数据的逻辑结构,数据的存储结构和数据运算结构。接下来的日子里我们研究的基本就是这些东西;

1 数据的逻辑结构

  指反映数据元素之间的逻辑关系的数据结构,其中的逻辑关系是指数据元素之间的前后件关系,而与他们在计算机中的存储位置无关。 逻辑结构包括:   ①、集合:数据结构中的元素除了同属一个集合之外,他们之间没有其他的关系;

  ②、线性:由0个或多个元素组成的有限数列,元素之间的关系为一对一;

  ③、:元素之间的关系为一对多,有且仅有一个特定的称为根(root)节点,是n个节点的有限级,当n为0时,称为空树;

  ④、:由顶点的有穷非空集合组成,通常表示为G(V,E),其中,G表示一个图,V是图G中顶点的集合,E是图中边的集合。元素之间的关系为多对多;

2 数据的存储结构

  指数据的逻辑结构在计算机存储空间的存放形式。数据的物理结构是数据结构在计算机中的表示(又称映像)。由于具体实现的方法有顺序,链式,散列表等形式,所以一种数据逻辑结构可表示成一种或多种存储结构;   1、顺序存储:指把数据元素放在存储地址连续的存储单元;      优点:有序,增加和查询的时间复杂度O(1);     缺点:正因为有序所以在插入和删除时需要整体后移或前移,故时间复杂度为O(n);无法确定线性结构存储数据的长度;   2、链式存储:指把数据元素任意的放在地址的任意存储单元上,这组存储单元为可连续,也可为不连续;     优点:无序,插入和删除时操作物理空间简便,值需更换引用或指针,时间负责度为O(1);     缺点:增加和查询时需要的遍历,所以时间复杂度为O(n);

二、算法

1、什么是算法?

  为了让计算机做出各种各样的处理,我们需要编写程序。为了让编写的程序“更加可靠、更加高效”,我们必须了解大量的算法,那么算法是什么?   听到算法这个词,大部分人都觉得好像很晦涩。的确,这不是一个常常能听到的词。事实上,在数学、计算机等理工科领域,所谓的算法,指的就是“对待问题的解决步骤”。而这里说的特定问题,通常有:


  • 对信息进行排序
  • 搜索目标信息

  等不同的问题。   此外,如果说“算法是解决问题的步骤”,那么撇开计算机的数据处理不论,现实生活中也有很多问题的解决方法蕴含了算法的思想,比如菜谱。   而编写一段计算机程序一般都是实现一种已有的方法来解决某个问题。这种方法大多和使用的编程语言无关——它适用于各种计算机以及编程语言。是这种方法而非计算机程序本身描述了解决问题的步骤。在计算机科学领域,我们用算法这个词来描述一种有限、确定、有效的并适合用计算机程序来实现的解决问题的方法。

2、为什么学算法?

  工作中经常会遇到各种问题,而这些问题大多都可以使用算法来解决并提升程序性能和存储,比如求1+2+…+9999+10000的和?   一般程序员:

int i, sum = 0, n = 10000;
for(i=1; i <= n; i++){
    sum = sum + i;
}
System.out.print(sum);

  学过算法的程序员:

int i, sum = 0, n = 10000;
sum = (1+n)*n/2;
System.out.print(sum);

  可能以计算机的神速,两个算法都可以秒杀解决掉!但是,如果我们把条件换成1加到1千万,或者1加到1千亿,差距就可想而知了,甚至人脑都可以比电脑计算得快了,所以对于走技术这条路上的程序猿来说,学算法还是非常有必要的。

3、算法的特性

  输入:算法具有零个或多个输入;   输出:算法至少有一个或多个输出;   有穷性:指算法在执行有限的步骤之后,自动结束而不会出现无限循环,并且每一个步骤在可接受的时间内完成;   确定性:算法的每一个步骤都具有确定的含义,不会出现二义性;   可行性:算法的每一步都必须是可行的,也就是说,每一步都能够通过执行有限次数完成;

4、算法衍生的概念

时间复杂度

  在进行算法分析时,语句总的执行次数T(n)是关于问题规模n的函数,进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度,也就是算法的时间量度,记作:T(n)= O(f(n))。它表示随问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同,称作算法的渐近时间复杂度,简称为时间复杂度。其中f(n)是问题规模n的某个函数。   这样用大写O()来体现算法时间复杂度的记法,我们称之为大O记法。一般情况下,随着输入规模n的增大,T(n)增长最慢的算法为最优算法

第一种算法:
int i, sum = 0, n = 100;   // 执行1次
for( i=1; i <= n; i++ )    // 执行了n+1次
{
sum = sum + i;          // 执行n次
}

第二种算法:
int sum = 0, n = 100;     // 执行1次
sum = (1+n)*n/2;          // 执行1次

  第一种算法的时间复杂度为O(n),第二种算法的时间复杂度为O(1);   

常见的时间复杂度

空间复杂度

  算法的空间复杂度通过计算算法所需的存储空间实现,算法的空间复杂度的计算公式记作:S(n)=O(f(n)),其中,n为问题的规模,f(n)为语句关于n所占存储空间的函数。   通常,我们都是用“时间复杂度”来指运行时间的需求,是用“空间复杂度”指空间需求。当直接要让我们求“复杂度”时,通常指的是时间复杂度。   显然对时间复杂度的追求更是属于算法的潮流!   通常,我们在写代码时,完全可以用空间换时间,提高性能。

三、常用的数据结构

  描述算法的时候所使用的数据结构的种类丰富多彩。以下这些是其中最具代表性的,之后都会总结到:

1. 数组

  把同类数据紧密排列就得到“数组”。数据排列成一条直线的数组叫一维数组,数据项长方形一样纵横排列的数组叫二维数组,数据像长方体一样排列的数组叫三维数组。

2. 链表

  “链表”是和“数组”一样,在管理按顺序排列的数据的时候使用的数据结构,链表通过详解橙子一样的方式按顺序或者逆序管理前后关联的数据(这里的有序并不是按照一定规则的有序,而是排列的有序,就像排队一样,并不是按照年龄大小,身高的有序,而是逻辑次序上的有序)。

3. 堆栈

  “堆栈”可以用于管理像堆积在桌子上的书本一样的数据。这种管理方式是:取数据的顺序和存数据的顺序相反(“先进后出”)。

4. 队列(等待队列)

  “队列”对数据的管理方式就像是超时收银台前排的队一样,按照排队的先后顺序处理数据。也就是说,这种管理方式里,取数据和存数据的顺序是一致的(“先进先出”)。

5. 树(树木的结构)

  书可以从树干分出两三个枝干,从某一个枝干上又可以分出两三个枝干。像树木结构一样管理数据的数据结构就叫做“树”。

 本系列参考书籍:

  《写给大家看的算法书》

  《图灵程序设计丛书 算法 第4版》

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据库

用SQL高性能解决字符串的连续匹配

高性能解决有序集合的连续匹配问题 场景: A集合有8个元素:ali、boy、c、dog、e、f、g、h, B集合有5个元素:boy、c、dog、e、h 问B中...

1999
来自专栏Albert陈凯

MapReduce编程思想通俗理解

综述 Map(映射)与Reduce(化简)来源于LISP和其他函数式编程语言中的古老的映射和化简操作,MapReduce操作数据的最小单位是一个键值对。用户在使...

2988
来自专栏LinkedBear的个人空间

【挑战剑指offer】系列02:替换空格 原

本系列的算法原题来自于“牛客网-剑指offer”,写这个板块,不仅仅是解决算法问题本身,更是手动提高难度、自行变式,思考更多的解决方案,以带给自己一些启发。

1163
来自专栏程序员互动联盟

【答疑解惑】失之毫厘谬以千里

1、scanf使用陷阱 ? ? 如果scanf中%d是连着写的如“%d%d”,在输入数据时,数据之间不可以加逗号,只能是空格或tab键或者回车键“1 2” 或 ...

2967
来自专栏机器学习算法与Python学习

长文 | 手把手教你如何使用python进行数据分析(最好将文章代码自己码一遍)

关键字全网搜索最新排名 【机器学习算法】:排名第一 【机器学习】:排名第二 【Python】:排名第三 【算法】:排名第四 原文 http://www.cnbl...

3765
来自专栏开发技术

排序之快速排序(下)

快排上是可以进行优化的,那么可以进行哪些优化了,是不是和你想的一样了? 我们往下看

1212
来自专栏云时之间

算法导论系列:分治算法

说起分治法,大家一定也都听过秦始皇采用郡县制将国家分为三十六郡的故事,我们常说”山高皇帝远”,意思就是山高路远,皇帝都管不了,实际上无论皇帝多远,山有多高,整个...

1172
来自专栏take time, save time

你所能用到的数据结构(三)

三、对于效率提高的初次尝试     对于最自然的几种排序算法,数学家们开始思考如何提高排序算法的效率,可以通过数学证明出来如果想达到这个目的,必须想办法将相距...

2807
来自专栏我杨某人的青春满是悔恨

函数式思维

自从大四看了三章《SICP》之后我就自诩为一个函数式编程爱好者,之前也在公司分享过一个 Haskell 的 Topic,效果非常糟糕,讲到后来已经没剩几个人了,...

921
来自专栏一个会写诗的程序员的博客

用 Kotlin 的函数式编程 替代 GOF 设计模式用 Kotlin 的函数式编程 替代 GOF 设计模式函数式编程(FP)《Kotlin极简教程》正式上架:

"函数式编程", 又称泛函编程, 是一种"编程范式"(programming paradigm),也就是如何编写程序的方法论。它的基础是 λ 演算(lambda...

1204

扫码关注云+社区