中国建设学会网站,泉州建设网站制作,企业融资案例,网络技术服务创作不易#xff0c;感谢三连#xff01;
一、算法
1.1 什么是算法 算法(Algorithm):就是定义良好的计算过程#xff0c;他取一个或一组的值为输入#xff0c;并产生出一个或一组值作为输出。简单来说算法就是一系列的计算步骤#xff0c;用来将输入数据转化成输出结果。… 创作不易感谢三连
一、算法
1.1 什么是算法 算法(Algorithm):就是定义良好的计算过程他取一个或一组的值为输入并产生出一个或一组值作为输出。简单来说算法就是一系列的计算步骤用来将输入数据转化成输出结果。
1.2 算法的效率 算法在编写成可执行程序的时候运行的时候需要耗费时间资源和空间资源。因此衡量一个算法的效率就是从时间和空间两个维度来衡量的我们把他细分出了两个概念——时间复杂度和空间复杂度。 时间复杂度主要衡量一个算法的运行快慢而空间复杂度主要衡量一个算法运行所需要的额外空间。在计算机发展的早期计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。也就是说现如今的我们判断算法的好坏重点是判断他的时间复杂度在条件允许的情况下我们也会非常乐意用空间去换时间。
二、时间复杂度
2.1 时间复杂度的概念 在计算机科学中算法的时间复杂度是一个函数它定量描述了该算法的运行时间。一个算法执行所耗费的时间从理论上说是不能算出来的只有你把你的程序放在机器上跑起来才能知道。但是我们需要每个算法都上机测试吗是可以都上机测试但是这很麻烦所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例算法中的基本操作的执行次数为算法的时间复杂度。
即找到某条基本语句与问题规模N之间的数学表达式就是算出了该算法的时间复杂度。
// 请计算一下Func1中count语句总共执行了多少次
void Func1(int N)
{
int count 0;
for (int i 0; i N ; i)
{for (int j 0; j N ; j){count;}
}for (int k 0; k 2 * N ; k)
{count;
}
int M 10;
while (M--)
{count;
}
printf(%d\n, count);
}
Func1时间复杂度F(N)N^22*N10
N 10时F(N) 130 N 100时F(N) 10210 N 1000时F(N) 1002010
当N取越大时2*N以及10对FN的影响越来越小而影响最大的是N^2,所以引入了大O的渐进表示法即计算一个大概的次数就行。
2.2 大O的渐进表示法
大O符号Big O notation是用于描述函数渐进行为的数学符号。推导大O阶方法 1、用常数1取代运行时间中的所有加法常数。函数中只有常数 2、在修改后的运行次数函数中只保留最高阶项。 3、如果最高阶项存在且不是1则去除与这个项目相乘的常数。得到的结果就是大O阶。使用大O的渐进表示法以后
Func1的时间复杂度为ON
N 10时F(N) 100 N 100时F(N) 10000 N 1000时F(N) 1000000
大O的渐进表示法去掉了那些对结果影响不大的项简洁明了的表示出了执行次数。
另外有些算法的时间复杂度存在最好、平均和最坏情况 最坏情况任意输入规模的最大运行次数(上界) 平均情况任意输入规模的期望运行次数 最好情况任意输入规模的最小运行次数(下界)例如在一个长度为N数组中搜索一个数据x 最好情况1次找到 最坏情况N次找到 平均情况N/2次找到在实际中一般情况关注的是算法的最坏运行情况所以数组中搜索数据时间复杂度为O(N)
2.3 为什么要考虑最坏情况卡瑞尔公式 我是这样理解的时间复杂度也是人为设计的参考了心理学上的卡瑞尔公式即接收最坏的往往才能有最好的
卡瑞尔公式强迫自己接受最坏的情况首先在精神上接受它然后集中精力从容解决问题从根本上抹除忧虑甚至有时候能给你带来惊喜。
最坏情况下的时间复杂度是算法在任何输入实例上运行时间的界限这就保证了算法的运行时间不会比最坏情况更长 。
三、空间复杂度
空间复杂度也是一个数学表达式是对一个算法在运行过程中临时占用存储空间大小的量度 。
空间复杂度不是程序占用了多少bytes的空间因为这个也没太大意义所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟实践复杂度类似也使用大O渐进表示法。
注意函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。
四、常见的复杂度对比 五、时间复杂度和空间复杂度例题
特点时间一去不复返但是空间可以重复利用
// 计算Func3的时间复杂度
void Func3(int N, int M)
{int count 0;for (int k 0; k M; k){count;}for (int k 0; k N ; k){count;}printf(%d\n, count);
} ON // 计算Func4的时间复杂度
void Func4(int N)
{int count 0;for (int k 0; k 100; k){count;}printf(%d\n, count);
} O1 // 计算阶乘递归Fac的时间复杂度
long long Fac(size_t N)
{if(0 N)return 1;return Fac(N-1)*N;
} 每次调用函数都是O1的复杂度调用N次就是ON的复杂度 // 计算阶乘递归Fac的时间复杂度
long long Fac(size_t N)
{if(0 N)return 1;for(int i0;iN;i)
{
……
}return Fac(N-1)*N;
} 递归函数第一次执行了N次循环第二次执行N-1次循环以此类推最后执行N次时结束所以调用总次数为等差数列求和NN1/2,时间复杂度是O(N^2) // 计算斐波那契递归Fib的时间复杂度和空间复杂度
long long Fib(size_t N)
{if(N 3)return 1;return Fib(N-1) Fib(N-2);
} 最左侧会逐步减少到Fib1有N层但是右侧未必能走到N层所以呈现的三角形并不是等腰三角形。但是不影响大O阶表示时间复杂度ON^2 时间一去不复返但是空间是可以重复利用的新销毁的函数栈帧释放后可以马上被新的函数栈帧替代重复利用的空间所以空间复杂度是ON // 计算BubbleSort的时间复杂度和空间复杂度
void BubbleSort(int* a, int n)
{assert(a);for (size_t end n; end 0; --end){int exchange 0;for (size_t i 1; i end; i){if (a[i-1] a[i]){Swap(a[i-1], a[i]);exchange 1;}}if (exchange 0)break;}
}
嵌套for循环所以时间复杂度是ON^2,虽然每次循环都有存在创建i和end变量但其实使用的都是一块空间空间一直在被重复利用所以空间复杂度O1
六、二分查找法
6.1 时间复杂度
// 计算BinarySearch的时间复杂度
int BinarySearch(int* a, int n, int x)
{assert(a);int begin 0;int end n-1;// [begin, end]begin和end是左闭右闭区间因此有号 while (begin end){int mid begin ((end-begin)1);if (a[mid] x)begin mid1;else if (a[mid] x)end mid-1;elsereturn mid;}return -1;
} 如上图空间复杂度是logN 6.2 效率以及实用性 7、内存、外存、CPU、缓存的一些相关知识
7.1 内存和外存的区别
内存快、小、8G-16G左右、带电存储
外存慢、大、500G左右、不带电存储 cpu只能在内存访问要想访问外存就得先把数据拿到内存中去运行速度会比较慢所以我们平时处理数据都是在内存中处理的处理之后要存储时才会拿到外存中保存起来这其实和文件操作很类似文件也是属于外存可以永久化地保存数据。 举个例子我们打开word写论文在word还没保存的时候该数据是存储在内存的缓存中的如果这个时候突然断电那么数据在缓存中没有及时保存到外存里就会造成数据丢失而如果我们保存在外存里即使断电也不会出现数据丢失。
7.2 数据结构和数据库 我们学习数据结构的本质意义是帮助我们在内存中管理数据而因为不同的数据结构有不同的特点对应着不同的需求所以没有一种数据结构可以完美的解决所有的问题因此需要学习大量的数据结构类型根据场景和需要去使用 而我们在外存中管理数据就是通过数据库、文件。
7.3 CPU、寄存器、三级缓存 一般我们CPU在访问内存数据的时候需要优先将数据放在寄存器或者三级缓存中。
寄存器是最快的但是一般只有4-8字节的大小对于大一点的数据一般都是加载到缓存中再由cpu进行读取。
缓存命中率在说明这两个问题之前。我们需要要解一个术语 Cache Line。缓存基本上来说就是把后面的数据加载到离自己近的地方对于CPU来说它是不会一个字节一个字节的加载的因为这非常没有效率一般来说都是要一块一块的加载有利于提高缓存命中率的对于这样的一块一块的数据单位术语叫“Cache Line”一般来说一个主流的CPU的Cache Line 是 64 Bytes也有的CPU用32Bytes和128Bytes64Bytes也就是16个32位的整型这就是CPU从内存中捞数据上来的最小数据单位。
所以cpu在读取数据的时候如果在缓存中找到该数据就可以直接处理这种情况就是缓存命中率高。而如果在缓存中找不到该数据那么就需要先从内存中加载到缓存里再读取数据这种情况就是缓存命中率低。
对于数组而言由于其连续存放的特点CPU在访问第一个数据的时候会顺便把后面的数据加载进缓存而CPU访问第二个数据的时恰好第二个数据就在缓存甚至可能第三个、第四个数据都在缓存取决于cpu的处理数据容量所以数组顺序表的缓存命中率高而对于链表来说各个结点直接在物理结构上不存在连续所以即使cpu加载了后续的空间大概率也是无用的所以链表的缓存命中率低。并且无用的数据还挤占了原先缓存区的位置容易造成缓存污染。
八、顺序表和链表的再总结
顺序表
优点1、下标随机访问排序、二分查找 2、cpu高速缓存命中率高
缺点1、指定位置插入和删除元素效率低下 2、扩容存在效率损失还可能存在一定的空间浪费
应用场景适用于高效存储以及频繁访问的场景
链表
优点1、任意位置插入和删除效率都高 2、按需申请和释放不存在空间的浪费
缺点1、不支持下标的随机访问 2、cpu告诉缓存命中率低
应用场景适用于频繁任意位置插入和删除的场景
