做网站都需要租服务器吗婺源网站建制作

当前位置： 首页 > news >正文

做网站都需要租服务器吗,婺源网站建制作,wordpress fatal error,百度推广平台登录网址欢迎各位来到 Harper.Lee 的学习世界#xff01; 博主主页传送门#xff1a;Harper.Lee的博客主页 想要一起进步的uu欢迎来后台找我哦#xff01; 本片博客主要介绍的是数据结构中关于算法的时间复杂度和空间复杂度的概念。 一、算法 1.1 什么是算法#xff1f; 算法(Alg… 欢迎各位来到 Harper.Lee 的学习世界 博主主页传送门Harper.Lee的博客主页 想要一起进步的uu欢迎来后台找我哦 本片博客主要介绍的是数据结构中关于算法的时间复杂度和空间复杂度的概念。 一、算法 1.1 什么是算法 算法(Algorithm):就是定义良好的计算过程他取一个或一组的值为输入并产生出一个或一组值作为输出。简单来说算法就是一系列的计算步骤用来将输入数据转化成输出结果。 1.2 算法的复杂度 算法在编写成可执行程序后运行时需要耗费时间资源和空间(内存)资源 。因此衡量一个算法的好坏一般是从时间和空间两个维度来衡量的即时间复杂度和空间复杂度。         时间复杂度主要衡量一个算法的运行快慢而空间复杂度主要衡量一个算法运行所需要的额外空间。在计算机发展的早期计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展计算机的存储容量已经达到了很高的程度计算机的配置变得越来越高对内存空间复杂度的关注也就没那么高了。所以我们如今已经不需要再特别关注一个算法的空间复杂度。目前计算机行业的硬件方面已经遇到瓶颈期了。 摩尔定律其核心内容是当价格不变时集成电路上可容纳的晶体管数目约每隔18个月至24个月便会增加一倍同时性能也将提升一倍。换言之每一美元所能买到的电脑性能将每隔18个月翻两倍以上。这一定律揭示了信息技术进步的速度为半导体行业的发展提供了长期的发展目标和预测。 二、时间复杂度 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 执行的基本操作次数 FNN^22*N10 N 10              F(N) 130            N^2 100 N 100            F(N) 10210,           N^2 10000 N 1000          F(N) 1002010,       N^2 1000000 从这个例子我们发现当N越大当N趋于无穷大时,N^2对时间复杂度的结果影响最大。因此我们选择大概估算大O的渐进表示法的方法忽略掉2*N10这一项时间复杂度就可以表示为FNON^2。当N很小的时候认为时间复杂度一样没有比较的意义CPU主频很大。CPU主频在 2.3 有详细介绍 2.2 大O的渐进表示法 大概估算是计算算法属于哪个量级level。 大O符号Big O notation是用于描述函数渐进行为的数学符号。推导大O阶方法 1、用常数1取代运行时间中的所有加法常数。 2、在修改后的运行次数函数中只保留最高阶项。 3、如果最高阶项存在且不是1则去除与这个项目相乘的常数。得到的结果就是大O阶。 使用大O的渐进表示法以后Func1的时间复杂度为FNON^2         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 为什么On使用最坏情况下的估算结果呢 在这种情况下实际的结果要么就是估算的结果的惊喜要么就刚好是最低预期结果这是一种以防万一的心态在预估了所有坏的可能后得到的方案。 2.4 CPU主频拓展 CPU主频也称为时钟频率或时钟速度是指中央处理单元(CPU)内部时钟的频率或速度。         它表示了处理器每秒钟执行指令的次数通常以赫兹(Hz)为单位表示例如兆赫兹(MHz)或千兆赫兹(GHz)。主频是评估其性能和速度的一个重要指标之一。一般来说较高的主频意味着处理器能够更快地执行指令因此在一定程度上具有更高的性能。然而主频并不是评估处理器性能的唯一因素其他因素如微架构、核心数量、缓存大小、指令集等也会影响性能。需要注意的是主频并不是唯一影响处理器性能的因素。不同型号的处理器可能在相同主频下表现出不同的性能因为它们的架构和其他规格可能不同。因此在选择计算机或处理器时不仅要考虑主频还要综合考虑其他因素以确保满足你的性能需求。 资料来自百度 CPU主频也叫时钟频率单位是MHz用来表示CPU的运算速度。         CPU的工作频率主频包括两部分外频与倍频两者的乘积就是主频。         倍频的全称为倍频系数。CPU的主频与外频之间存在着一个比值关系这个比值就是倍频系数简称倍频。倍频可以从1.5一直到23以至更高以0.5为一个间隔单位。外频与倍频相乘就是主频所以其中任何一项提高都可以使CPU的主频上升。由于主频并不直接代表运算速度所以在一定情况下很可能会出现主频较高的CPU实际运算速度较低的现象。因此主频仅仅是CPU性能表现的一个方面而不代表CPU的整体性能 。         处理器主频以每秒处理器周期可运行的百万次计算。通常具有较高MHz或GHz的处理器能够提高电脑运行创新、娱乐、通信和生产力应用的性能。但主频只是影响系统整体性能的一个方面主频高的机器整体性能并非就一定高。                          声明此段文本复制自博客http://t.csdnimg.cn/FGGi7 简而言之CPU主频反映了在一个周期内大概能执行多少指令主频越高CPU的处理速度越快。CPU性能再怎么差它每秒的运算速度也能运行上亿次。可以利用clock函数验证 #include time.hint main() {int begin1 clock();int n 100000000;int x 10;for (int i 0; i n; i){x;}int end1 clock();printf(%d\n, x); printf(程序运行时间%d ms\n, end1 - begin1);return 0; } ​ 如果结果为0ms说明中间的时间消耗小于1ms而不是没有时间消耗。 C语言中的函数clock()它可以捕捉从程序开始运行到clock()被调用时所耗费的时间。两个clock()函数的返回值相减就可以计算两个函数之间的程序运行所消耗的大概时间(ms)了。我么可以利用它来大致测试一下电脑的性能。而且release版本做了优化因此时间比Debug版本稍短。 ​ 2.5 常见的时间复杂度量级 2.6 重要时间复杂度计算 2.6.1 冒泡排序的时间复杂度 On^2 Fnn-1 (n-2) (n-3)……321nn-¹⁄₂ 可以根据两个数比较的次数来写, 时间复杂度为On^2。注意不能直接数循环的个数。 // 计算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;} } 2.6.2 qsort函数的时间复杂度On*logn qsort函数的时间复杂度为 Onlogn 2.6.3 二分查找的时间复杂度 折半查找nn/2n/2/2……n/2/2/……/2查找了x次就除以x个2,2^xN所以xlogN省略底数2。最坏情况查找区间只剩一个数或者找不到。OlogN // 计算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)//beginend还有一个数{int mid begin ((end - begin) 1);//此写法可以防止溢出if (a[mid] x)begin mid 1;//因为签】前一次比较中mid已经比较过了else if (a[mid] x)end mid - 1;//end是mid-1elsereturn mid;}return -1; }//写法二 int BinarySearch(int* a, int n, int x) {assert(a);int begin 0;int end n - 1;// [begin, end) -保持左闭右开区间while(beginend){//int mid begin ((end - begin) 1);//防止溢出beginend值可能很大//也可以写成int mid (begin end)/2;(不能防止溢出)if (a[mid] x)begin mid 1;else if (a[mid] x)end mid;//这里变成endmid,而不是 mid-1elsereturn mid;}return -1; } 二分查找OlogN随着N的增长OlogN变化不大暴力查找ON随着N的增长ON变化很大。 缺点二分查找外强中干在实际中不太实用需要排序、而且数组结构不方便插入删除数据会造成数据整体的挪动。 2.6.4  strchr函数的时间复杂度 // 计算strchr的时间复杂度 const char * strchr ( const char * str, int character ); 在一个字符串中查找一个字符它的实现过程就相当于如下的代码 while (*str) {if (*str character)return str;elsestr; } 最好情况O1最坏情况On平均情况O123……n/n。所以时间复杂度为On。 时间复杂度的意义帮助我们对比几种解决方法孰优孰劣。  三、 常见时间复杂度的举例 1、On只看循环次数且系数对结果影响不大 Fn2*n10 , On而不是O2*n。Fn相当于只看循环次数,要去掉系数2即使这个系数是200也要去掉,系数对结果影响不大n无穷大时n和2*n没有区别。 // 计算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); } 2、On可以用多个未知数表示 FnMN,  OMN或Omax(M,N)。在时间复杂度经常使用N作为未知数也可以使用其它符号来表示未知数。如果M远大于NO(M)如果如果N远大于MO(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); } 3、Fn 常数,  O1 时间复杂度是O1而不是O100。没有未知数而只有常数次则时间复杂度为  O1。 // 计算Func4的时间复杂度 void Func4(int N) {int count 0;for (int k 0; k 100; k){count;}printf(%d\n, count); } 4、单身狗题目回顾为下一道题做铺垫 5、力扣–17.04. 消失的数字 题目描述数组nums包含从0到n的所有整数但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗 思路1先排序冒泡排序、qsort快速排序再查找如果前一个值(b)不等于后一个值(a) 1那么前一个值(b)就是消失的数字。由于时间复杂度现可以直接抛弃该思路排序ab; a1b但时间复杂度不符合要求。 思路2先将0~N进行求和然后再依次减去数组中值剩下的值就是消失的数字。时间复杂度为ON。缺陷N太大存在溢出风险 int missingNumber(int* nums, int numsSize){int N numsSize;//0~n一共n1个数但缺了1个数一共n个数int ret (0 N) * (N 1) / 2;//计算出0~n的总和for(int i 0; i numsSize; i)//{ret - nums[i];//总和减去数组中值}return ret; } 思路3按位异或相同为0相异为1有点类似于单身狗的那道题。On int missingNumber(int* nums, int numsSize){int N numsSize;int x 0;for(int i 0; i numsSize; i)//numsSize是少了1的9个数{x ^ nums[i];//0和任何数异或均是任何数} for(int j 0; j N; j)//这里有n个数10个数{x ^ j;}return x; } 6、力扣–189. 轮转数组 题目描述给定一个整数数组 nums将数组中的元素向右轮转 k 个位置其中 k 是非负数。  分析需要一个循环两个嵌套时间复杂度应该是Ok*N。 思路1暴力求解用只管的方式直接解 决问题不用太多技巧 表达式为FN N-1*N-1Ok * N 如果k为7或者7的倍数次,旋转7次或者7的倍数次其实就是旋转到原来的样子相当于不旋转如果旋转10次就相当于旋转了3次。所以真实的旋转次数为 k % N ;在最好情况下即没有旋转k % N 0 , O1;在最坏情况下KNN(N-1) k % N N-1ON^2,旋转N-1次。 值得注意的是时间复杂度必须要计算调用的其它方法所花的时间消耗。 void rotate(int nums, int numsSize, int k) {k%numsSize;while(k–)//k最大为n-1k–走了k次所以这里走了n-1次{//旋转一次 画图是最好的分析方法int tmp nums[numsSize-1];//最后一个数保存起来for(int i numsSize-2;i 0;i–)//起始位置在n-2numsSize-2结束情况i 0{nums[i1] nums[i];//中间过程}nums[0] tmp;}//但是用这种方法不能通过超出时间限制不能ON^2 }//前n-1个数往后挪 //循环分析循环就三个过程起始情况、中间过程、结束情况 思路2三段逆置  ON 代码如下  void reverse(int* a,int left,int right) {//三段逆置一定要画图,下标标明while(leftright)//一段区间左右往中间走未相遇交换值{int tmp a[left];a[left] a[right];a[right] tmp;left;–right;} }void rotate(int* nums, int numsSize, int k) {k% numsSize;reverse(nums,0,numsSize-k-1);//前n-k个数最后一个下标n-k-reverse(nums,numsSize-k,numsSize-1);reverse(nums,0,numsSize-1); } strncpy是针对字符串的在这里不合适。   7、对数时间复杂度常见出现形式 时间复杂度OlogN void func(int n) {int x 0;for (int i 1; i n; i * 2){x;}printf(%d\n, x); } int main() {func(8);func(1024);func(1024*1024);return 0; } 分析1*22……*2 N假设循环走x次就是x个2相乘2^xN两边同时取对数得到 。时间复杂度就是O。因为写的时候需要支持专业公式否则不好写底数。为了方便 省略了底数2直接写成了但是其他的就不能省略且其他底数的很少出现。 8、阶乘递归的时间复杂度 // 计算阶乘递归Fac的时间复杂度 long long Fac(size_t N) {if(0 N)return 1;return Fac(N-1)*N; } 每次调用函数都是O1的复杂度调用N次就是ON的复杂度而不是ON。如果变式时间复杂度为ON^2。  //变式 // 计算阶乘递归Fac的时间复杂度 long long Fac(size_t N) {if(0 N)return 1;for(int i 0; i N;i){//……}return Fac(N-1)N; } 总结递归时间复杂度为所有递归调用消耗次数相当于运算次数的累加。 9、斐波那契递归和非递归的时间复杂度 斐波那契递归非递归的时间复杂度ON^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 。分析过程如下图 斐波那契非递归斐波那契数列的优化的时间复杂度
// 1 1 2 3 5 8…. // 时间复杂度O(N)很大的优化 long long Fib(size_t N) {long long f1 1;long long f2 1;long long f3 0;for (size_t i 3; i N; i){f3 f1 f2;f1 f2;f2 f3;}return f3; } 其实斐波那契数列没什么特别的实用意义因为数据稍稍大点就计算不出结果了。50都不得行了。此外还可以使用字符串进行存储大树运算。 四、空间复杂度 4.1 空间复杂度定义  空间复杂度也是一个数学表达式是对一个算法在运行过程中临时占用存储空间大小的量度          空间复杂度不是程序占用了多少bytes的空间因为这个也没太大意义所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟实践复杂度类似也使用大O渐进表示法。         注意函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。 4.2 空间复杂度例题 1、冒泡排序的空间复杂度 变量个数3常数个所以空间复杂度为O1。空间复杂度计算的是为了解决这个问题而额外初选的空间 因此此算法中的数组不计算空间。 // 计算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;} } 2、  轮转数组另一个解法空间复杂度 不用三段逆置的方法重新创建一个数组后k个旋转在前面再把前n-k个拷贝到后面去 最后再将最终结果拷贝到原来的位置。此时新创建的N个数组就是为了解决此问题而创建的它就需要计算空间空间复杂度就是ON。 最后的代码如下代码中使用了变长数组 void _rotate(int* nums, int numsSize, int k, int* tmp) {k % numsSize;int n numsSize;memcpy(tmp, nums n - k, sizeof(int) * k);memcpy(tmpk, nums, sizeof(int) * (n-k));memcpy(nums,tmp, sizeof(int) * (n)); }void rotate(int* nums, int numsSize, int k) {int tmp[numsSize];_rotate(nums, numsSize, k, tmp); }3、阶乘递归的空间复杂度 // 计算阶乘递归Fac的空间复杂度 long long Fac(size_t N) {if (N 0)return 1;return Fac(N - 1) * N; } 4、斐波那契数列的空间复杂度为 常见的空间复杂度中只有三种O1、ON、ON^2比如二维数组。 创作不易喜欢的uu三连支持一下叭