数据结构疑问


1.时间复杂度O(1)与O(n)的区别?

image-20210316215804952

image-20210316220103135

2.随机存取

根据存储位置是否可计算(是否有一个计算地址的公式)来判断该数据结构是否具备随机存取的特性,如数组知道首地址就可计算后面所有元素的地址

第四章 数组和特殊矩阵

对一个文件的压缩的内在逻辑是否就是对稀疏矩阵的压缩处理?

文件压缩有很多种,包含了稀疏矩阵

为什么顺序存储的顺序表是依靠数组这个载体实现的,但是数组却不能看做线性结构的推广,对他进行插入和删除

数组是静态数据结构,本质上没有插入和删除运算

为什么稀疏矩阵压缩存储后,必会失去随机存取功能?

因为在这种矩阵中,非零元素的分布是没有规律的,为了压缩存储,就将每一个非零元素的值和它所在的行、列号做为一个结点存放在一起,这样的结点组成的线性表中叫三元组表,它已不是简单的向量,所以无法用下标直接存取矩阵中的元素(没有一个计算公式)。

动态数组是先申请一块指定大小的内存块区域,还是先申请一块未定义大小的内存区域之后再定义?

先申请一块指定大小的内存块区域

动态数组是数组吗?如果是,数组是静态数据结构,那动态数组也是静态数据结构吗?
image-20210318140952671

无论是动态数组还是静态数组,数组长度确定下来后存储空间就确定了,所以静态和动态数组都是静态数据结构

静态数据结构通常不会去定义插入、删除操作

image-20210318141309092

假如数组下标不是从0开始,而是从1开始,会影响到什么?

lacation计算里会出现一个-1计算

n和t都是未知常数,那O(n+t)复杂度和O(1)有什么区别?稀疏矩阵的快速转置算法中时间复杂度O(n+t)能不能直接写成O(n)?

n、t都是可变的,是变量,所以不能写成O(1),又不知道n、t哪个大,所以不能写成O(n)或者O(t).在某些情况下,如果知道n,t的大小情况的话是可以写成O(较大的那个)

我们学习的存储稀疏矩阵的方法是利用三元组,有没有更节省存储空间的办法或者更易进行矩阵运算的存储方式?

更节省空间的暂无

更易进行矩阵运算的有很多(分块啥的)

用数组存储矩阵,我们讨论了转置算法,那么对于其他的矩阵运算,比如求逆,点乘等,是否也有常用的算法?如果是用三元组存储的稀疏矩阵又要怎么进行这些矩阵运算?
如何实现稀疏矩阵的乘法运算,和平常的矩阵乘法运算相比,时间复杂度能否较为简单?

可以查查matlab是怎么实现的

C语言中的数组的定义和数据结构中的数组是否相同?C语言中的数组有何局限性?
image-20210318140758524
稀疏矩阵的快速转置算法“快速”的代价是什么?

存储空间增加了

稀疏矩阵的快速转置算法中,num和k数组的初始化都是必要的吗

按书上那么做的话是必要的

image-20210318152228362


文章作者: Ab4nd0n
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 Ab4nd0n !
评论
 上一篇
博客发布时 hexo d 命令报错 博客发布时 hexo d 命令报错
问题描述: 博客闲置了一段时间,最近想在上面记录一些自己遇到的问题和学习上的一些东西,hexo s正常,但是hexo g后进行hexo d时报错: fatal: unable to access ‘https: [//github.com/
2021-03-17
下一篇 
【数据结构】单链表的基本运算实现 【数据结构】单链表的基本运算实现
【数据结构】单链表的基本运算实现 关于数据结构中线性表的链接表示的基本运算的实现,把书上单链表的代码敲了一遍,加了些注释。 /* author:Ab4nd0n Time:2021-3-11 */ #include <std
2021-03-12
  目录