小菜数据结构于算法学习之路

小咪咪 2022-10-02 02:55 106阅读 0赞

在看数据结构与算法时，我的心情无比忐忑，无比纠结．在程序或者说项目设计之初，架构师会进行概要详细

设计，抽象类，实现类，接口等等，然后对这些进行封装，设计算法（还有很多的步骤，可参考项目开发流程

），而算法的设计取决于数据逻辑结构，算法的实现取决于物理存储结构．什么是数据逻辑结构和物理存储结

构，一头雾水的我便开始了下面的学习：

数据结构（Data Structure）：

数据结构包含逻辑结构和存储结构，以及对数据的各种操作（处理方法－－算法　于　处理结果－－数据类型

）；它是具有特定关系的数据元素的集合．  
数据类型的抽象定义：抽象的数据类型可以更容易的描述现实世界，如用线性表描述学生成绩表，用树或图描

述遗传关系或城市交通关系．定义格式如下：  
ADT 抽象数据类型名\{

数据对象：<数据对象的定义>

数据关系：<数据关系的定义>

基本操作：<基本操作的定义>

\}ADT 抽象数据类型名

逻辑结构包含集合结构，线性结构，树状结构和图状结构，常用的高效数据结构是数据表和树．

而物理存储结构则是指逻辑结构的物理镜像．存储结构又分为顺序存储结构和链式存储结构，物理存储结构是

数据结构在计算机中的表示．计算机中存储信息的最小单位是：位，８位是一个字节，两个字节是一个字符，

字节，字符或更多的二进制位可称为位串．在逻辑描述中，把位串称为元素或结点．

对于数据结构，以下简称DS（Date Structure）有：

DS=(　D，S　)　D是数据元素的集合，S是在D上的关系集合

另有：

P:( D，S )-----> M P是物理存储结构，M是存储区

数据结构DS的物理结构P对应于从DS的数据元素到存储区M（维护着逻辑结构S）的一个映射．

算法（Algorithm）：

算法表示某一特定类型的问题求解;

具有５个特性：

1　有穷性，表示算法必须总是（对任何合法的输入值）在执行有穷步之后结束，且每一步都在有穷的时间内完

成  
２　确定性　表示算法中每一条指令必须有确切的含义  
３　输入　Input  
４　输出　Output  
５　可行性　算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的  
算法设计要求：  
　　正确性、可读性、健壮性、效率与低存储量需求  
在设计程序的时候，我们往往会考虑到性能的问题，同样的问题，如果不考虑性能，或许会有很多中解决方案

，但是在同样配置的计算机，得到同样的结果的程序，一个几秒，另一个的几分钟，相信大家的选择不言而喻

，那在设计之初，如何确定程序的性能呢？于是就有了时间复杂度（Time Complexity）的计算．

Time Complexity:

T(n)=0(f(n))

"0"表示随问题规模的增大，算法执行增长率和f(n)的增长率相同，'0'表示数量级．  
实例：  
ispass(int num\[4\]\[4\]) ｛  
int i,j;  
for(i=0;i<4;i++)  
for(j=0;j<4;j++)  
if(num\[i\]\[j\]!=i\*4+j+1)  
return 0;  
return 1;  
\}  
最好情况：T（4）=O（0）　　　　　　　　　　　最坏情况：T（4）=O（n\*n）  
还有另一个重要的标示就是存储空间需求，空间复杂度可以作为算法所需存储空间的量度．  
记做：  
　　　　　　　　　S（n）=0（f（n））  
若额外空间相对于输入数据量来说是常数，则称此算法为原地工作。  
如果所占空间量依赖于特定的输入，则除特别指明外，均按最坏情况来分析。  
还是有很多地方不懂，也不知哪里有错．望大牛多多指导啊

转载于:https://blog.51cto.com/yangctoweb/617510

发表评论取消回复

表情：

评论列表（有 0 条评论，106人围观）

还没有评论，来说两句吧...

相关阅读

相关数据结构与算法学习之算法入门笔记

计算关于计算： > 对象：规律、技巧。 > > 目标：高效、低耗。 Computer science ------ Computing science 算法：特

深藏阁楼爱情的钟/ 2023年07月13日 15:14/ 0 赞/ 40 阅读

相关考研学习之数据结构排序算法学习

一.直接插入排序 1.1代码 include <stdio.h> / 直接插入排序 / void insertSort

谁借莪１个温暖的怀抱￠/ 2022年12月15日 15:29/ 0 赞/ 136 阅读

相关小菜数据结构于算法学习之路

在看数据结构与算法时，我的心情无比忐忑，无比纠结．在程序或者说项目设计之初，架构师会进行概要详细设计，抽象类，实现类，接口等等，然后对这些进行封装，设计算法（还有很多的步骤

小咪咪/ 2022年10月02日 02:55/ 0 赞/ 107 阅读

相关数据结构之Dijkstra算法

基本思想通过Dijkstra计算图G中的最短路径时，需要指定起点s(即从顶点s开始计算)。此外，引进两个集合S和U。S的作用是记录已求出最短路径的顶点(以及相应的最短路

た入场券/ 2022年09月23日 03:48/ 0 赞/ 191 阅读

相关我的算法学习之路

http://www.cricode.com/1808.html 转者注：看完这个，感觉很是惊异，自己的算法基础几乎为0...以此共勉原文作者：[Lu

╰半橙微兮°/ 2022年08月11日 13:28/ 0 赞/ 62 阅读

相关算法学习之路（一）——数据抽象

前言本文根据Algorithms（《算法》）一书，介绍算法的基础知识，围绕数据抽象，介绍了包括背包、队列和栈三种集合类数据类型的定义以及代码实现，最后讲解了链表的相关定

系统管理员/ 2022年05月14日 20:26/ 0 赞/ 144 阅读

相关数据结构之KMP算法

一. 首先求next值例如：模式串 a b a a b c a c next值 0 1 1 2 2 3 1 2 next

拼搏现实的明天。/ 2022年05月10日 14:08/ 0 赞/ 217 阅读

相关《数据结构与算法之美》学习笔记之开篇

> 本系列是极客时间中前 Google 工程师王争《数据结构与算法之美》专栏的学习笔记，想加强数据结构及算法能力的同学可以直接购买此专栏，[跳转链接在此][Link 1]

比眉伴天荒/ 2022年03月16日 05:52/ 0 赞/ 236 阅读

相关算法学习之路|PAT Ranking

Programming Ability Test (PAT) is organized by the College of Computer Science and Techn

ゝ一纸荒年。/ 2022年02月05日 06:17/ 0 赞/ 207 阅读

相关数据结构学习之最小生成树算法

数据结构学习之最小生成树算法 0x1 生成树的概念一个连通图的生成树(连通无回路图)是一个极小连通子图,其中含有图中的全部顶点,和n-1条边。 0x2 最

ゝ一世哀愁。/ 2021年11月10日 16:12/ 0 赞/ 288 阅读