时间复杂度与空间复杂度
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
文章目录
-
什么是数据结构
-
什么是算法
-
算法效率
-
时间复杂度
-
空间复杂度
-
常见时间复杂度以及复杂度 oj 练习
一、什么是数据结构
数据结构
(Data Structure)
是计算机存储、组织数据的方式指相互之间存在一种或多种特定关系的数据元素的集合。
内存中存储管理数据的结构--数据结构
数据结构和数据库的区别
本质上都是存储管理数据
数据结构--在内存中存储管理数据
数据库--在磁盘中存储管理数据
二、什么是算法
算法
(Algorithm):
就是定义良好的计算过程他取一个或一组的值为输入并产生出一个或一组值作为输出。简单来说算法就是一系列的计算步骤用来将输入数据转化成输出结果。
三、算法效率
算法在编写成可执行程序后运行时需要耗费时间资源和空间(
内存
)
资源 。因此
衡量一个算法的好坏一般是从时间和空间两个维度来衡量的
即时间复杂度和空间复杂度。
时间复杂度主要衡量一个算法的运行快慢而空间复杂度主要衡量一个算法运行所需要的额外空间。在计算机发展的早期计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。
四、时间复杂度
时间复杂度的定义在计算机科学中算法的时间复杂度是一个函数
它定量描述了该算法的运行时间。一个算法执行所耗费的时间从理论上说是不能算出来的只有你把你的程序放在机器上跑起来才能知
道。但是我们需要每个算法都上机测试吗是可以都上机测试但是这很麻烦所以才有了时间复杂度这个
分析方式。一个算法所花费的时间与其中语句的执行次数成正比例
算法中的基本操作的执行次数为算法
的时间复杂度。
即找到某条基本语句与问题规模N之间的数学表达式就是算出了该算法的时间复杂度。
大
O
的渐进表示法
大O符号
Big O notation
是用于描述函数渐进行为的数学符号。
推导大O
阶方法
1、用常数
1取代运行时间中的所有加法常数。
2、在修改后的运行次数函数中只保留最高阶项。
3、如果最高阶项存在且不是
1
则去除与这个项目相乘的常数。得到的结果就是大
O阶。
使用大O
的渐进表示法以后
Func1的时间复杂度为
N = 10 F(N) = 100
N = 100 F(N) = 10000
N = 1000 F(N) = 1000000
通过上面我们会发现大O
的渐进表示法
去掉了那些对结果影响不大的项
简洁明了的表示出了执行次数。
另外有些算法的时间复杂度存在最好、平均和最坏情况
最坏情况任意输入规模的最大运行次数(
上界)
平均情况任意输入规模的期望运行次数
最好情况任意输入规模的最小运行次数(
下界)
例如在一个长度为N
数组中搜索一个数据x
最好情况1次找到
最坏情况N次找到
平均情况N/2次找到
在实际中一般情况关注的是算法的最坏运行情况所以数组中搜索数据时间复杂度为O(N)
练习
注意
因为要在文本中写对数不好写而时间复杂度中log2N经常出现所以我们会将其简化成logN。而在有些书籍或者博客资料等等会简写成lgN。
五、空间复杂度
空间复杂度也是一个数学表达式是对一个算法在运行过程中
临时占用存储空间大小的量度
。
空间复杂度不是程序占用了多少
bytes
的空间因为这个也没太大意义所以空间复杂度算的是变量的个数。
空间复杂度计算规则基本跟实践复杂度类似也使用
大
O
渐进表示法
。
注意
函数运行时所需要的栈空间
(
存储参数、局部变量、一些寄存器信息等
)
在编译期间已经确定好了因
此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。
练习
注意
时间是累积的空间是不累积的可以重复利用。
六、常见时间复杂度以及复杂度oj练习
一般常见复杂度
int missingNumber(int* nums, int numsSize){
int x=0;
//利用异或的特性对同一个值异或两次等于它本身
for(int i=0;i<numsSize;i++){
x^=nums[i];
x^=i;
}
return x^numsSize;
}
int missingNumber(int* nums, int numsSize){
int *a;
a=(int*)malloc(sizeof(int)*(numsSize+1));
for(int i=0;i<=numsSize;i++)
a[i]=-1;
for(int i=0;i<numsSize;i++){
a[nums[i]]=nums[i];
}
for(int i=0;i<=numsSize;i++)
if(a[i]==-1)
return i;
return -1;
}
void reverse(int*nums,int left,int right)
{
while(left<right){
int temp=nums[left];
nums[left]=nums[right];
nums[right]=temp;
++left;
--right;
}
}
void rotate(int* nums, int numsSize, int k){
//首先将后k个数进行逆置
//然后将前n-k个数进行逆置
//最后整体逆置即可
k=k%numsSize;
reverse(nums,numsSize-k,numsSize-1);
reverse(nums,0,numsSize-k-1);
reverse(nums,0,numsSize-1);
}