一 . 数据结构前言
1.1 数据结构
数据结构(Data structure) 是计算机存储,组织数据的方式,指互相之间存在一种或多种特定关系的数据元素的集合。没有一种单一的数据结构对所有用途都有用,所以要学习各式各样的数据结构,如:线性表,树,图,哈希等。(不仅能存储数据,还能够管理数据)
1.2 算法
算法 ( Algorithm) : 就是定义良好的计算过程 , 取一个或一组的值输入,并产生处一个或一组值作为输出 。 (一系列的计算步骤 , 用来将输入数据转化成输出结果)
数据结构和算法不分家 ----> 数据存储在内存中 , 需要有算法 ; 有算法的地方 ,需要存储和管理数据(数据结构);
二 . 算法效率
如何衡量一个算法的好坏 ? ----> 代码简洁?时间短?
看以下例题 :
旋转数组 : . - 力扣(LeetCode)
void rotate(int* nums, int numsSize, int k) {
while (k--) {
int end = nums[numsSize-1];
for (int i = numsSize-1; i > 0; i--) {
nums[i] = nums[i - 1];
}
nums[0] = end;
}
}
代码测试可以通过 , 但是点击提交的时候却无法通过 ,在面对大量的数据 , 超出了时间限制 ,就说明这个算法 , 还不太好 , 那该怎样去衡量一个算法的好坏呢 ?
算法在编写成可执行程序后 , 运行时需要耗费时间资源和空间(内存资源)。这么看来 ,衡量一个算法的好坏 , 一般是从时间和空间两个维度来衡量 ,即时间复杂度和空间复杂度。
时间复杂度主要衡量一个算法的运行快慢 。 而空间复杂度主要衡量一个算法运行所需要的额外空间 。
在计算机发展早期 , 计算机的存储容量很小 。 所以对空间复杂度很是在乎 。 但是经过计算机行业的迅速发展 , 计算机的存储容量已经达到了很高的程度 ,而对算法空间复杂度的关注度有所下降。
三 . 时间复杂度
定义 : 在计算机科学中 , 算法的时间复杂度是一个函数式 T(N) , 它定量描述了该算法的运行时间 。 时间复杂度是衡量程序的时间效率 , 那么为什么不去计算程序的运行时间呢?
使用clock 函数计算时间 代码如下:
#include <stdio.h>
#include <time.h>
int main()
{
int t1 = clock();//当前时间
//程序运行到当前程序的一个时间
for (int i = 0; i < 100000; i++)
{
for (int j = 0; j < 100000; j++)
{
int a = 1;
}
}
int t2 = clock();
printf("%d\n", t2 - t1);
return 0;
}
三次执行的时间都不相同 , 程序执行的时间不仅和编译器有关 , 而且还和CPU 的计算速度有关 ,并不能准确的计算出算法的运行的时间
为什么不去计算程序的运行时间呢?
- 因为程序运行时间和编译环境和运行机器的配置都有关系 , 比如同一个算法程序 , 用一个老编译器 和 新编译器编译 , 在同样机器下运行时间不同。
- 同一个算法程序 ,用一个老低配置机器和新高配置机器 , 运行时间也不同。
- 并且时间只能程序写好后测试 , 不能写程序之前通过理想思想计算来评估。
时间复杂度是一个函数式 T(N) 到底是什么
思考:
所以只需要计算程序能代表增长量的大概执行次数 ,复杂度的表示通常使用 大O的渐进表示法;
3.1 大O的渐进表示法:
大 O 符号 (Big O notation) : 是用于描述函数渐进行为的数学符号
推导大O阶规则:
- 时间复杂度函数时T(N) 中 ,只保留最高阶的项 , 去掉最低阶的项 ; 因为N不断变大,低阶项对结果影响越来越小 , 但N无穷大时 , 就可以忽略不计了。
- 如果高阶项存在 并且系数不是1 , 则可以去掉这个项目的常数项系数 , 因为当N不断增大的时候,这个系数对结果的影响越来越小,当N无穷大的时候,就可以忽略不计了。
- T(N) 中如果没有N相关的项目 , 只有常数项 , 用常数项1取代所有加法常数
所以 , 以上例题的时间复杂度是 O(n^2)
3.2 示例1:
3.3 示例2:
3.4 示例3:
3.5 示例4:
在有些算法的时间复杂度存在最好 , 平均 ,和最坏情况
最坏情况 : 任意输入规模的最大运行次数(上界)
平均情况 : 任意输入规模的期望运行次数
最好情况 : 任意输入规模的最小运行次数(下界)
大O的渐进表示法在实际中一般情况关注的是算法的上界 , 也就是最坏运行情况。
3.5 示例5:
3.6 示例6: