【数据结构和算法】时间复杂度和空间复杂度

简介: 一、前言二、时间复杂度2.1时间复杂度表示形式2.1.1规则:3.1如何计算时间复杂度3.1.1线性阶3.1.2平方阶3.1.3对数阶常见的时间复杂度排序:三、空间复杂度3.1Java的基本类型内存占用

一、前言


数据结构和算法是程序的灵魂,这是某位程序员大佬所言,学习了这门,我们便可以在


编程之路越走越远。时间复杂度一般是我们所关心的。


二、时间复杂度


时间复杂度简单的说就是一个程序运行所消耗的时间,叫做时间复杂度,我们无法目测


一个程序具体的时间复杂度,但是我们可以估计大概的时间复杂度。


一段好的代码的就根据算法的时间复杂度,即使在大量数据下也能保持高效的运行速


率,这也是我们学习算法的必要性。


2.1时间复杂度表示形式


一般用O()来表示算法的时间复杂度,我们叫做大O记法。


2.1.1规则:


①用常数1取代运行时间中的所有的加法常数。比如,一个程序中有十条输出语句


我们不会记成O(10),而是用O(1)来表示。


②如果最高阶项不是1,那么去掉最高阶阶项,因为我们认为数字在后期影响不大。


如O(8n),则时间复杂度应该为O(n)。


③只保留最高阶项,如O(3n^2+6n+2),则时间复杂度为O(n^2)


3.1如何计算时间复杂度


计算时间复杂度主要看执行的次数和输入的关系


3.1.1线性阶


顾名思义,就是输入和输出成正比。


       for(int i=0;i<n;i++){
            sum+=i;
       } 


当n=1,执行一次,当n=100,执行100次 ,所以当为n时,执行n次,所以时间复杂度为

O(n)


3.1.2平方阶

for(int i=0;i<n;i++){
   for(int j=0;j<n;j++){
    }
}


外层for循环和内层for循环都是时间复杂度时n外层循环一次,内层循环n次,所以时间复杂度是


O(n^2)。


另一种:


for(int i=0;i<n;i++){
   for(int j=0;j<i;j++){
    }
}


外层复杂度是n,内层是1+2+...+n-1+n,所以是n(1+n)/2,由大O法得时间复杂度是O(n^2).


3.1.3对数阶


int i=0;n=100;
while(i<n){
i=i*2;
}


满足条件时,程序运行了,先设X个2相乘后大于n,则2^X=n,解得X=log2(n),所以时间


复杂度时O(log2(n)),log以2为底,n为真数。



常见的时间复杂度排序:


O(1)< O(log2(n))< O(n)< O(nlog2(n)< O(n^2)< O(n^3)< O(2^n)< O(n!)< O(n^n)


一般来说,到了O(n^2)及以上数据量大时运行效率极低,所以数据量大时,应选用更有的算法


三、空间复杂度


简单的说就是程序运行所需要的空间。


写代码我们可以用时间换空间,也可以用空间换时间。加大空间消耗来换取运行时间


的缩短加大时间的消耗换取空间,我们一般选择空间换时间。一般说复杂度是指时间复杂度


3.1Java的基本类型内存占用


微信图片_20220106111233.png


计算机访问内存都是一次一个字节。


一个引用(机器地址)需要8个字节表示


如 Date date=new Date();则date这个变量需要8字节表示。


一般内存的使用,如果不够8字节,都会自动填充8字节(也就是8的整数倍)


目录
相关文章
|
16天前
|
存储 机器学习/深度学习 算法
C 408—《数据结构》算法题基础篇—链表(下)
408考研——《数据结构》算法题基础篇之链表(下)。
79 29
|
16天前
|
存储 算法 C语言
C 408—《数据结构》算法题基础篇—链表(上)
408考研——《数据结构》算法题基础篇之链表(上)。
72 25
|
16天前
|
存储 人工智能 算法
C 408—《数据结构》算法题基础篇—数组(通俗易懂)
408考研——《数据结构》算法题基础篇之数组。(408算法题的入门)
58 23
|
1月前
|
存储 算法 测试技术
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
51 2
|
4天前
|
DataX
☀☀☀☀☀☀☀有关栈和队列应用的oj题讲解☼☼☼☼☼☼☼
### 简介 本文介绍了三种数据结构的实现方法:用两个队列实现栈、用两个栈实现队列以及设计循环队列。具体思路如下: 1. **用两个队列实现栈**: - 插入元素时,选择非空队列进行插入。 - 移除栈顶元素时,将非空队列中的元素依次转移到另一个队列,直到只剩下一个元素,然后弹出该元素。 - 判空条件为两个队列均为空。 2. **用两个栈实现队列**: - 插入元素时,选择非空栈进行插入。 - 移除队首元素时,将非空栈中的元素依次转移到另一个栈,再将这些元素重新放回原栈以保持顺序。 - 判空条件为两个栈均为空。
|
1月前
|
存储 C语言 C++
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
142 77
|
1月前
|
C++
【C++数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】
【数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】(1)遇到左括号:进栈Push()(2)遇到右括号:若栈顶元素为左括号,则出栈Pop();否则返回false。(3)当遍历表达式结束,且栈为空时,则返回true,否则返回false。本关任务:编写一个程序利用栈判断左、右圆括号是否配对。为了完成本关任务,你需要掌握:栈对括号的处理。(1)遇到左括号:进栈Push()开始你的任务吧,祝你成功!测试输入:(()))
38 7
|
1月前
|
存储 C++ 索引
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
【数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】初始化队列、销毁队列、判断队列是否为空、进队列、出队列等。本关任务:编写一个程序实现环形队列的基本运算。(6)出队列序列:yzopq2*(5)依次进队列元素:opq2*(6)出队列序列:bcdef。(2)依次进队列元素:abc。(5)依次进队列元素:def。(2)依次进队列元素:xyz。开始你的任务吧,祝你成功!(4)出队一个元素a。(4)出队一个元素x。
44 13
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
|
1月前
|
存储 C语言 C++
【C++数据结构——栈与队列】链栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现链栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储整数,最大
46 9
|
3月前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
99 5

热门文章

最新文章