Advertisement

引入数据结构的同时关注常用的内存消耗

阅读量:

【近期重新梳理了数据结构的相关知识,遂整理成文以作记录。个人见解难免存在不足之处,还望读者不吝赐教。

数据结构本质上是指数据在内存中的组织与存储形式。
依据物理存储特性(即数据在内存中实际的存放方式),主要可以划分为顺序存储结构与链式存储结构

从逻辑层面来看,可将其分为以下几类:
集合结构、线性结构、树状结构以及图状结构

关于算法的时间复杂度
通常采用大O记法进行描述,表示为:
O(f(n))

先给出结论:

  1. 将运行过程中出现的常数项替换为1;
  2. 仅保留最高阶项;
  3. 去除最高阶项的系数。

举例说明如下:
3 → O(1)
n+3 → O(n)
n²+2 → O(n²)

我对时间复杂度的理解是,在不断放大n的前提下,忽略那些对整体规模影响较小的因素,如加法中的常数项或低阶项等,最终只关注对整体规模起决定性作用的部分,例如最高阶项。

下面简单介绍一些常见的大O记法
这些记法的核心在于n的不同幂次方,因为这正是决定时间复杂度的关键因素。

  1. 线性阶:单层循环操作,对应的时间复杂度为 O(n);
  2. 平方阶:双层嵌套循环操作,则为 O(n²);
  3. 立方阶:三层嵌套循环操作,则为 O(n³);

全部评论 (0)

还没有任何评论哟~