网站建设专家怎么样,代刷网站怎么做,天元建设集团有限公司的商业承兑汇票能按时支付吗,wordpress实现付费浏览链表和顺序表的优劣分析及其时间、空间复杂度分析 一、链表和顺序表的优劣分析二、算法复杂度font face 楷体 size 5 color blue//上面算法的执行次数大致为#xff1a;F#xff08;N#xff09; N^22*N10; N 10,F(10) 1002010 130次 N 1… 链表和顺序表的优劣分析及其时间、空间复杂度分析 一、链表和顺序表的优劣分析二、算法复杂度font face 楷体 size 5 color blue//上面算法的执行次数大致为FN N^22*N10; N 10,F(10) 1002010 130次 N 100,F(100) 1000020010 10210次 N 1000,F(10) 100000200010 1002010次 实际中我们计算时间复杂度时我们其实并不一定要计算精确的执行次数而只需要大概执行次数那么这里我们使用大O的渐进表示法。 /font font face 楷体 size 5 color blue//大O渐进表示法 一、链表和顺序表的优劣分析
1.顺序表的优劣分析 //优势 //*下标可以随机访问顺序表的底层是数据可以下标随机访问 //CPU高速缓存命中率高这个还是很重要 可以看这篇文章理解CPU缓存知识 什么是缓存 缓存是一种在计算机系统中用于存储数据的硬件或软件组件它的主要目的是提高数据访问的速度和效率。缓存通常位于CPU内部或主存储器和CPU之间它能够快速地存储和检索经常访问的数据和指令。当CPU需要访问数据或指令时它会首先检查缓存中是否已经存在相应的数据或指令如果存在则可以直接从缓存中读取这样就避免了从主存储器中读取数据或指令的延迟。 缓存的设计允许它牺牲数据的实时性以空间换时间从而减少数据库的IO操作减轻服务器压力减少网络延迟加快页面打开速度。缓存可以分为不同的层次如CPU缓存、操作系统文件缓存和浏览器缓存等。 CPU缓存分为L1 Cache一级缓存和L2 Cache二级缓存它们位于CPU内部用于存储CPU即将使用的指令和数据。操作系统文件缓存用于存储操作系统读取的文件数据而浏览器缓存则用于存储用户访问的静态或动态页面内容以便在用户再次访问时能够快速加载。 总的来说缓存是一种重要的性能优化技术它通过将数据存储在更接近处理器或数据源的位置提高了数据处理的效率和响应速度。 //大概意思是在CPU附近会有三级缓存L1,L2,L3 //L1缓存分为两种指令缓存和数据缓存),L2和L3缓存不分指令和数据 //L1和L2缓存在每一个CPU核中L3则是所有CPU核心共享的内存。 //L1、L2、L3的越离CPU近就越小速度也越快越离CPU远速度也越慢。 //缓存是速度最快的存储数据的地方 //后面存储数据的地方就是存储器和磁盘 //下面看看各个存储硬件的存储速度 L1 的存取速度4 个CPU时钟周期 L2 的存取速度11个CPU时钟周期 L3 的存取速度39个CPU时钟周期 RAM内存的存取速度107 个CPU时钟周期 //缓存命中问题 //我们需要要解一个术语 Cache Line。缓存基本上来说就是把后面的数据加载到离自己近的地方对于CPU来说它是不会一个字节一个字节的加载的因为这非常没有效率一般来说都是要一块一块的加载的对于这样的一块一块的数据单位术语叫“Cache Line”一般来说一个主流的CPU的Cache Line 是 64 Bytes也有的CPU用32Bytes和128Bytes64Bytes也就是16个32位的整型这就是CPU从内存中捞数据上来的最小数据单位。 //也就是说CPU在取数据计算的时候至少是取一个缓存行64Bytes)的大小这样顺序表的物理地址连续加载到缓存中CPU取到的都是顺序表中存的有效数据而链表的物理空间不连续大概率只能取到一个有效数据其它供CPU计算的数据没用所谓的缓存命中不高 //缺点 //前面部分的插入删除需要挪动数据效率低下 //扩容效率损失可能还存在一定的空间浪费 --------------------------------------- 2.链表最优结构的比较的优劣分析 //优势 //任意位置的插入删除效率都很高 //按需申请释放不存在浪费 //劣势 //不支持下标随机访问 //CPU高速缓存命中率低可以理解为 cache line 取数据问题
二、算法复杂度
//算法在编写成可执行程序后运行时需要消耗时间资源和内存空间资源衡量一个算法的好坏要存运行时间的多少和空间消耗大小来衡量一个算法的好坏 //时间复杂度主要衡量一个算法的运行快慢而空间复杂度主要衡量一个算法运行所需要的额外空间。在计算机发展的早期计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。 时间复杂度 时间复杂度的定义在计算机科学中算法的时间复杂度是一个函数它定量描述了该算法的运行时间。一个算法执行所耗费的时间从理论上说是不能算出来的只有你把你的程序放在机器上跑起来才能知道。但是我们需要每个算法都上机测试吗是可以都上机测试但是这很麻烦所以才有了时间复杂度这个 分析方式。一个算法所花费的时间与其中语句的执行次数成正比例算法中的基本操作的执行次数为算法的时间复杂度。 即找到某条基本语句与问题规模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;
}//上面算法的执行次数大致为FN N^22*N10; N 10,F(10) 1002010 130次 N 100,F(100) 1000020010 10210次 N 1000,F(10) 100000200010 1002010次 实际中我们计算时间复杂度时我们其实并不一定要计算精确的执行次数而只需要大概执行次数那么这里我们使用大O的渐进表示法。 //大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) //考虑最坏情况来写时间复杂度 //上面时间复杂度为ON^2
// 计算Func2的时间复杂度
void Func2(int N)
{int count 0;for (int k 0; k 2 * N ; k){count;}int M 10;while (M--){count;}printf(%d\n, count);
}//时间复杂度O(N)
// 计算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);
}//时间复杂度O(MN
// 计算Func4的时间复杂度
void Func4(int N)
{int count 0;for (int k 0; k 100; k){count;}printf(%d\n, count);
}//O(1) --常数次用O(1)表示
// 计算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;}
}//冒泡的时间复杂度怎么算 //这个还是想一下假设有N个元素最坏排序多少趟能排好 // N-1 // N-2 // N-3 // … // 3 // 2 // 1 //总共执行了多少次 // N-1) * (1N-1)/2 (N-1) * N/2 1/2*(N^2-N); // 则冒泡排序的时间复杂度O(N^2)
// 计算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;
}//二分查找的时间复杂度为多少 //怎么理解二分查找算法的时间复杂度 //假设有一个长度为N的数组查找一个数最坏情况是什么 //最坏情况是查找的数只剩一个或没有二分查找的实质是每次缩小一半区间来查找 //查找N个数则每查找一次少一半的数 则N/2/2/2…/2 1;区间缩小了多少次也就是除了多少个2就是查找了几次 //设除了x个2 N/2^x 1; N 2^x; x logN //所以二分查找算法最坏情况下查找log以2为底N的对数 //时间复杂度为O(logN); ----------------------------------------- 计算下面递归阶乘的时间复杂度
// 计算阶乘递归Fac的时间复杂度
long long Fac(size_t N)
{if(0 N)return 1;return Fac(N-1)*N;
}//所谓的递归多次开辟函数栈桢的过程那么看一次开辟的栈桢执行程序是多少次总共N次的递归的时间复杂度
long long F(size_t N)
{if (0 N)return 1;for (int i 0; i N; i){//...}return F(N - 1) * N;
}//计算上面算法的时间复杂度 //上面函数栈桢开辟了N1次每一次是O(N),所以总共是O(N^2) //总结一下递归算法计算时间复杂度每次递归子函数消耗累加起来
// 计算斐波那契递归Fib的时间复杂度
long long Fib(size_t N)
{if(N 3){return 1;}return Fib(N-1) Fib(N-2);
}// 2^0 // 2^1 // 2^2 // 2^3 // 2^(N-1) //: F(n) 2^0 2^1 2^2 … 2^(N-1) //:2*F(n) 2^1 2^2 2^3 … 2^N //:F(n) 2^N-1 //所以斐波那契的时间复杂度O(2^N) 什么是空间复杂度 空间复杂度也是一个数学表达式是对一个算法在运行过程中临时占用存储空间大小的量度 。 空间复杂度不是程序占用了多少bytes的空间因为这个也没太大意义所以空间复杂度算的是变量的个数。 空间复杂度计算规则基本跟时间复杂度类似也使用大O渐进表示法。 注意函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。 //空间复杂度算的是因为算法的需要额外开的空间
// 计算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;}
}//在上面的算法中额外开辟的空间变量有end,i,exchange,说一点在这儿i虽然开辟了n次,但是这儿申请释放的空间是同一块空间所以没有额外开辟空间 //所以此算法的空间复杂度是O(N); -----------------------------------------
// 计算阶乘递归Fac的空间复杂度
long long Fac(size_t N)
{if(N 0)return 1;return Fac(N-1)*N;}//空间复杂度就是计算算法额外开辟的空间 //此递归总共递归了(N1)次每次是O(1),总共是O(N);
// 计算斐波那契递归Fib的空间复杂度
long long Fib(size_t N)
{if(N 3){return 1;}return Fib(N-1) Fib(N-2);//斐波那契递归的空间复杂度怎么算 //这个比较复杂一点要理解一点函数栈桢的开辟才能做好 //综上分析虽然这个递归每一层很复杂但是利用的空间只有一个子函数的空间因此斐波那契的空间复杂度是O(N) 完结
