中冶东北建设网站,wordpress 静态页面显示文章,wordpress后台怎么进,wikidot网站怎么做目录 前言 一、复杂度的概念 二、时间复杂度 三、大O的渐进表示法 四、空间复杂度 五、常见复杂度对比 总结 前言 本文主要讲述数据结构中的算法复杂度 一、复杂度的概念 算法在编写成可执行程序后#xff0c;运行时需要耗费时间资源和空间(内存)资源。因此衡量一个算法的好坏… 目录 前言 一、复杂度的概念 二、时间复杂度 三、大O的渐进表示法 四、空间复杂度 五、常见复杂度对比 总结 前言 本文主要讲述数据结构中的算法复杂度 一、复杂度的概念 算法在编写成可执行程序后运行时需要耗费时间资源和空间(内存)资源。因此衡量一个算法的好坏一般是从时间和空间两个维度来衡量的即时间复杂度和空间复杂度。 时间复杂度主要衡量一个算法的运行快慢。空间复杂度主要衡量一个算法运行所需要的额外空间。 在计算机发展的早期计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注⼀个算法的空间复杂度。 二、时间复杂度 在计算机科学中算法的时间复杂度是一个函数式T(N)它定量描述了该算法的运行时间。时间复杂度是衡量程序的时间效率。 那么为什么不去计算程序的运行时间呢
因为程序运行时间和编译环境和运行机器的配置都有关系比如同一个算法程序用⼀个老编译器进行编译和新编译器编译在同样机器下运行时间不同。同一个算法程序用⼀个老低配置机器和新高配置机器运行时间也不同。并且时间只能程序写好后测试不能写程序前通过理论思想计算评估。
那么算法的时间复杂度是一个函数式T(N)到底是什么呢
答这个T(N)函数式计算了程序的执行次数。 通过c语言编译链接章节学习我们知道算法程序被编译后生成二进制指令程序运行就是cpu执行这些编译好的指令。那么我们通过程序代码或者理论思想计算出程序的执行次数的函数式T(N)假设每句指令执行时间基本一样(实际中有差别但是微乎其微)那么执行次数和运行时间就是等比正相关 这样也脱离了具体的编译运行环境。执行次数就可以代表程序时间效率的优劣。比如解决一个问题的算法a程序T(N)N算法b程序T(N)N^2那么算法a的效率⼀定优于算法b。 示例
//请计算⼀下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;}
}
画图表示 解析实际中我们计算时间复杂度时计算的也不是程序的精确的执行次数精确执行次数计算起来还是很麻烦的(不同的⼀句程序代码编译出的指令条数都是不⼀样的)计算出精确的执行次数意义也不大 因为我们计算时间复杂度只是想比较算法程序的增长量级也就是当N不断变大时T(N)的差别上面我们已经看到了当N不断变大时常数和低阶项对结果的影响很小所以我们只需要计算程序能代表增长量级的大概执行次数复杂度的表示通常使用大O的渐进表示法。 三、大O的渐进表示法
大O符号BigOnotation是用于描述函数渐进行为的数学符号 推导大O阶规则 时间复杂度函数式 T(N) 中只保留最高阶项去掉那些低阶项因为当 N 不断变大时 低阶项对结果影响越来越小当 N 无穷大时就可以忽略不计了。如果最高阶项存在且不是 1 则去除这个项目的常数系数因为当 N 不断变大这个系数对结果影响越来越小当 N 无穷大时就可以忽略不计了。T(N) 中如果没有 N 相关的项目只有常数项用常数 1 取代所有加法常数。 通过大O渐进表示法我们可以推出上述 Func1 的时间复杂度了因为主要是count的运行次数所以时间复杂度也是主要计算它的运行次数 示例1
//计算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
//计算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);
}
画面表示 解释如果MN则时间复杂度可以为O(M)反之NM则时间复杂度可以写成O(N)如果MN则时间复杂度为O(MN) 示例3
//计算Func4的时间复杂度void Func4(int N)
{int count 0;for (int k 0; k 100; k){count;}printf(%d\n, count);
}
画图表示 示例4
//计算strchr的时间复杂度const char* strchr(const char* str, int character)
{const char* p_begin str;while (*p_begin ! character){if (*p_begin \0)return NULL;p_begin;}return p_begin;
}
画图表示 通过上面我们会发现有些算法的时间复杂度存在最好、平均和最坏情况。 最坏情况任意输入规模的最大运行次数(上界)平均情况任意输入规模的期望运行次数平均情况任意输入规模的期望运行次数 大O的渐进表示法在实际中一般情况关注的是算法的上界也就是最坏运行情况。 因此示例4的时间复杂度应该为O(N) 示例5冒泡排序
//计算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;}
}
画图表示 示例6对数的计算
//求时间复杂度void func5(int n)
{int cnt 1;while (cnt n){cnt * 2;}
}
画图表示 注log 的底数可写可不写如果底数为10可写成 lg 示例7递归的计算
//计算阶乘递归Fac的时间复杂度long long Fac(size_t N)
{if (0 N)return 1;return Fac(N - 1) * N;
}
画图表示 四、空间复杂度 空间复杂度也是一个数学表达式是对一个算法在运行过程中因为算法的需要额外临时开辟的空间。 空间复杂度计算规则基本跟时间复杂度类似也使用大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;}
}
画图表示 示例2递归函数
//计算阶乘递归Fac的空间复杂度long long Fac(size_t N)
{if (N 0)return 1;return Fac(N - 1) * N;
}
画图表示 五、常见复杂度对比 常见的复杂度有n、logn、n*logn、n的平方、n的三次方、2的n次方、n的阶乘 解析很明显n的平方、n的三次方、2的n次方、n的阶乘这些复杂度都比较高。而n、logn、n*logn这些复杂度就比较低算法的效率比较高。 总结 以上就是本文的全部内容感谢支持
