数据结构

双子孤狼 2020-10-15 16:58:21 ⋅ 112 阅读

结构,简单的理解就是关系。严格点说,结构是指各个组成部分相互搭配和排列的方式。在现实世界中,不同数据元素之间不是独立的,而是存在特定的关系,我们将这些关系成为结构。

数据结构:是相互之间存在一种或多种特定关系的数据元素的集合。

按照视点的不同,我们把数据结构分为逻辑结构和物理结构

逻辑结构

指数据元素之间的相互关系

1. 集合结构

 

 

集合结构中的数据元素除了同属于一个集合外,他们之间没有其他的关系,各个数据元素是平等的
 
集合结构
2. 线性结构

线性结构中的数据元素之间是一对一的关系


 
线型结构
3. 树形结构

树形结构中的数据元素之间存在一对多的层级关系


 
树形结构
4. 图形结构

图形结构中的数据元素是多对多的关系


 
图形结构

物理结构

指数据的逻辑结构在计算机中的存储形式

1. 顺序存储结构

数据元素存放在连续的存储单元中,其数据间的逻辑关系和物理关系是一致的

2.链式存储结构

是把数据元素存放在任意的存储单元里,这组存储单元可以是连续的,也可以是不连续的。 数据的存储关系并不能反映其逻辑关系。

算法

算法是解决特定问题求解步骤的描述,在计算机中表现为指令的有限序列,并且每条指令表示一个或多个操作。

1. 算法特性

1.输入输出
2.有穷性 (时间)
3.确定性(不会出现二义性)
4.可行性 (可实现、可移植, 每一步都能够通过执行有限次数完成)

2. 算法设计的要求

1.正确性(输入、输出、加工处理无歧义,正确反映问题的需求,得到正确的答案)
2.可读性
3.健壮性
4.时间效率高和存储量低

3. 算法效率和度量方法

1.事后统计方法
2.事前分析估算方法

时间复杂度

推导大O阶:
1.用常数1取代运行时间中的所有加法常数
2.在修改后的运行次数函数中,只保留最高阶
3.如果最高阶项存在且不是1,则去除与这个项相乘的常数
1.常数阶

常数阶看代码执行的行数,假如有3行代码 则O(3) => O(1);

2.线性阶

线性阶是循环结构会复杂很多,要确定某个算法的阶次, 需要确定某个特定语句或语句集运行的次数。因此分析算法的复杂度,关键就是要分析循环结构的运行情况

for(int i = 0; I < n; i++) {
   /* 时间复杂度为O(1)的程序*/
}
时间复杂度为O(n)
3. 对数阶
int count = 1;
while(count < n) {
  count = count * 2;
  /* 时间复杂度为O(1)的程序*/
}
由于每次count乘以2之后,就距离n更近了一份。也就是说 有多少个2相乘后大于n,则会退出循环。 由2^x = n, 得到 x = log2^n, 所以时间复杂度为 O(log n)
4. 平方阶
for(int i = 0; i< m; i++) {
   for(int j = 0; j < n; j++) {
     /* 时间复杂度为O(1)的程序*/
  }
}
时间复杂度为 O(m x n)

int i , j;
for(i = 0; i< n; i++) {
   for( j = i; j < n; j++) {
     /* 时间复杂度为O(1)的程序*/
  }
}
时间复杂度为 O(n^2);
for(int i = 0; i < n; i ++) {
   function(i);
}

void function(int count) {
   print(count);
}
时间复杂度为O(n);
for(int i = 0; i < n; i ++) {
   function(i);
}

void function(int count) {
   int j;
   for( j = count; j < n; j++) {
        /* 时间复杂度为O(1)的程序*/
   }
}
时间复杂度为O(n^2);
 
常见的时间复杂度


作者:挽弓如月_80dc
链接:https://www.jianshu.com/p/4fa0bdb7a5e1
来源:简书
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

全部评论: 0

    我有话说:

    线性表 - 栈与队列

    1.栈 1.栈(stack)是限定仅在表尾进行插入和删除操作的线性表,(先进后出) 2.我们把允许插入和删除的一端成为栈顶(top) 另一端称为栈底(bottom),不含任何数据元素的栈称为空栈

    玩转ES6(三):数据结构

    Set 是ES6提供的一种新的数据结构,它允许你存储任何类型的唯一值,而且Set中的元素是唯一的。

    线性表 - 循环链表

    1.引子 单链表解决了从A 查找到E的过程,假设现在要求从E 查找到A,用时最短, 因为单链表是单向的,只能从前往后,无法解决这个问题。因此引出了循环链表。   思路图 将单链表的终端结点的指针由空指针改为头结点,就使...

    排序 --- 归并排序

    此篇文章引自 这里,个人感觉无出其右者,只好借鉴而来 归并排序 是递归分治和有序合并的简称, 首先利用分治法的思想将序列递归分裂成若干个子序列,使将子序列基本有序,最后使整体有序。 一、图示过程 1、归并排序的流程   ...

    精品推荐:Java核心数据结构(List,Map,Set)使用技巧与优化

    JDK提供了一组主要的数据结构实现,如List、Map、Set等常用数据结构。这些数据都继承自 java.util.Collection 接口,并位于 java.util 包内。

    推荐一款前端数据源管理工具 algeb

    ALGEB 简介 这是一个比较抽象的库,一开始可能比较难理解。我写它的初衷,是创建可响应的数据请求管理。在传统数据请求中,我们只是把携带ajax代码的一堆函数放在一起,这样就可以调用接口。但是这种

    Dgraph 1.2.8 发布,事务性分布式图形数据库

    Dgraph 1.2.8 发布了。Dgraph 是一个可扩展的,分布式的,低延迟的图数据库,目标是提供 Google 生产水平的规模和吞吐量,在超过 TB 的结构数据里,为用户提供足够低延迟的实时

    搞对数据库连接池,这次从100优化到3ms!阿里架构师都说好

    我在研究HikariCP(一个数据库连接池)时无意间在HikariCP的Github wiki上看到了一篇文章(即前面给出的链接),这篇文章有力地消除了我一直以来的疑虑,看完之后感觉神清气爽。故在此

    为什么说作为程序员分库分表的必要性一定要掌握?

      互联网大厂程序员必须掌握海量数据和高并发问题处理技能,期望进入大厂的程序员一定要仔细看这篇! MySQL 分库分表是做什么的? 相信很多程序员对 MySQL 都比较熟悉了,目前国内

    CrateDB 4.3.1 发布,分布式 SQL 数据库

    CrateDB 4.3.1 预发布。Crate 是一个开源的大规模的可伸缩的数据存储系统,无需任何系统管理需求。提供强大的搜索功能。用于存储各种表格数据、非结构数据和二进制对象。并可通过 SQL

    Apache IoTDB 0.11.2 发布,物联网时序数据库

    Apache IoTDB 0.11.2 现已发布。Apache IoTDB 是一个集成数据专为时间序列数据设计的管理引擎。它为用户提供以下服务:数据收集、存储和分析。由于其轻巧的结构,高

    京东技术:多数据模型数据库 | 应用实例解析

    作 者 简 介吕信,京东商城技术架构部资深架构师,拥有多年数据产品研发及架构经验。

    MongoDB系列---数据类型/插入文档(三)

    ;3. 数字;4. 字符串;5. 数据;6. 对象...

    精品推荐:微服务架构下静态数据通用缓存机制

    在分布式系统中,特别是最近很火的微服务架构下,有没有或者能不能总结出一个业务静态数据的通用缓存处理机制或方案,这篇文章将结合一些实际的研发经验,尝试理清其中存在的关键问题以及探寻通用的解决之道。

    TypeScript Nodejs 项目结构

    新旧交替新事物代替旧事物无外乎旧事物太陈旧。JS动态软类型语言,便利的同时也带来了很多弊端,随着...

    TypeScript Nodejs 项目结构

    1. 新旧交替 新事物代替旧事物无外乎旧事物太陈旧。 JS动态软类型语言,便利的同时也带来了很多弊端,随着项目的增大,加上没有注释,你完全会懵逼。 可以看下网上汇总的错误信息,有多少个是类型错误引起的 图为rollbar统计的数千个项目中数...