写简历的网站,app手机软件开发公司,建站系统模板,成都营销型网站文章目录 #x1f680;一、算法的概念#x1f680;二、算法的特征1.可行性2.确定性3.有穷性4.输入5.输出 #x1f680;三、算法的评价1.正确性2.可读性3.健壮性 #x1f680;四、算法的复杂度⛳#xff08;一#xff09;时间复杂度1、时间复杂度的概念2、大O的渐进表示法… 文章目录 一、算法的概念二、算法的特征1.可行性2.确定性3.有穷性4.输入5.输出 三、算法的评价1.正确性2.可读性3.健壮性 四、算法的复杂度⛳一时间复杂度1、时间复杂度的概念2、大O的渐进表示法3、常见时间复杂度 ⛳二空间复杂度 一、算法的概念
算法algorithm是解决一系列问题的清晰指令也就是能对一定规范的输入在有限的时间内获得所要求的输出。
简单来说算法就是解决一个问题的具体方法和步骤。算法是程序的灵魂。
程序 算法数据结构二、算法的特征
1.可行性
算法中执行的任何计算步骤都可以分解为基本可执行的操作步即每个计算步都可以在有限时间里完成也称之为有效性
2.确定性
算法的每一步都要有确切的意义不能有二义性。例如“增加x的值”并没有说增加多少计算机就无法执行明确的运算。
3.有穷性
算法的有穷性是指算法必须在执行有限个步骤后终止。操作次数不宜过大不能超过人们事先设定的时间限制。
4.输入
算法有0个或多个输入以刻画运算对象的初始情况所谓0个输入是指算法已经给出了初始条件。
5.输出
一个算法可能有1个或多个输出以反映输入数据加工后的代码没有输出的算法是没有意义的
三、算法的评价
通常一个好算法应该达到如下目标
1.正确性
算法应该正确的解决问题。
2.可读性
算法应该具有较好的可读性让人们理解算法的作用。
3.健壮性
输入非法数据时算法也可以做出适当的反应而不会产生奇奇怪怪的输出。
四、算法的复杂度
算法复杂度是指算法在变为可执行程序后所耗费的时间资源和内存。
⛳一时间复杂度
1、时间复杂度的概念
评估程序所需要的时间。一个算法执行所耗费的时间从理论上说是不能算出来的只有你把你的程序放在机器上跑起来才能知道。但是我们需要每个算法都上机测试吗是可以都上机测试但是这很麻烦所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例算法中的基本操作的执行次数为算法的时间复杂度。 即找到某条基本语句与问题规模N之间的数学表达式就是算出了该算法的时间复杂度。 举例
Func1 执行的基本操作次数 F(N) N^2 2*N 10
当N越来越大的时候数字的大小主要取决于N^2了。实际中我们计算时间复杂度时我们其实并不一定要计算精确的执行次数而只需要大概执行次数那么这里我们使用大O的渐进表示法。
void Func1(int N)
{int count 0;for (int i 0; i N; i)//这个循环N^2次{for (int j 0; j N; j){count;}}for (int k 0; k 2 * N; k){count;} //这个循环2*N次int M 10;while (M--) //这个循环10次{count;}printf(%d\n, count);
}2、大O的渐进表示法
推导大O阶方法 1、用常数1取代运行时间中的所有加法常数。 2、在修改后的运行次数函数中只保留最高阶项。 3、如果最高阶项存在且不是1则去除与这个项相乘的常数。得到的结果就是大O阶。 使用大O的渐进表示法以后Func1的时间复杂度为 O(N^2)
另外有些算法的时间复杂度存在最好、平均和最坏情况 最坏情况任意输入规模的最大运行次数(上界) 平均情况任意输入规模的期望运行次数 最好情况任意输入规模的最小运行次数(下界) 例如在一个长度为N数组中搜索一个数据x 最好情况1次找到 最坏情况N次找到 平均情况N/2次找到 在实际中一般情况关注的是算法的最坏运行情况所以数组中搜索数据时间复杂度为O(N)
3、常见时间复杂度
复杂度标记符号说明常量O(1)操作数量为常数与输入数据的规模无关对数O(log2 n)与输入数据的比例是 log2n线性O(n)与输入数据成正比平方O(n²)与输入数据规模的比例为平方立方O(n³)与输入数据规模的比例为立方指数O(2ⁿ)O(kⁿ)O(n!)快速增长尽量减少这种代码
代码示范
实例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*N 10次而通过推导大O阶方法用常数1取代加法常数得到2*N 1,只保留最高阶项得到2*N,将最高阶项的系数变为1得到N
所以最后的时间复杂度是O(N)
实例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);
}时间复杂度为O(NM)
实例3
计算Func4的时间复杂度
void Func4(int N)
{int count 0;for (int k 0; k 100; k){count;}printf(%d\n, count);
}用常数1替代100时间复杂度是O(1)
实例4
计算strchr的时间复杂度
const char* strchr(const char* str, int character)
{while (*str ! character){str;}return str;
}最快执行了1次最慢执行了N次所以时间复杂度是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;}
}第一趟冒泡排序了N - 1次第二趟冒泡排序了N - 2次依次类推排序这个基本操作在最坏的情况下一共执行了(N-1)(N-2)…321次比较和交换操作。使用等差数列求和的公式可以将这个总次数简化为N(N-1)/2。而最好的情况下是数组已经排好了此时只需要执行N次时间复杂度取最坏的情况所以是O(N^2)
实例6
计算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 mid 1;else if (a[mid] x)end mid - 1;elsereturn mid;}return -1;
}假如有序数组有N个数那么查找一次就会将数组的范围缩小一半直到最后只剩下一个数
可以这么用数字表示
N / 2 / 2 / 2 / 2 / 2 / 2 … / 2 / 2 1
假设查找了x次也就是每次将数组缩小一半(除以2)这个基本操作执行了x次那么这个x与N之间的关系是2^x N
那么x logN这里默认底数为2
所以时间复杂度是O(logN)
实例7
计算阶乘递归Fac的时间复杂度
long long Fac(size_t N)
{if (0 N)return 1;return Fac(N - 1) * N;
}基本操作递归了N次每一层的计算时间复杂度是常数时间。所以时间复杂度为O(N)
实例8
计算斐波那契递归Fib的时间复杂度
long long Fib(size_t N)
{if (N 3)return 1;return Fib(N - 1) Fib(N - 2);
}基本操作递归了约为2^N次根据推到大O阶的方法所以最后的时间复杂度为O(N)
⛳二空间复杂度
空间复杂度也是一个数学表达式是对一个算法在运行过程中临时占用存储空间大小的量度空间复杂度不是程序占用了多少bytes的空间因为这个也没太大意义所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟实践复杂度类似也使用大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;}
}可见红框标注的地方是在函数的内部额外创建了4个变量也就是开辟了常数个额外空间所以空间复杂度为O(1)
实例2
计算Fibonacci的空间复杂度
// 返回斐波那契数列的前n项
long long* Fibonacci(size_t n)
{if (n 0)return NULL;long long* fibArray (long long*)malloc((n 1) * sizeof(long long));fibArray[0] 0;fibArray[1] 1;for (int i 2; i n; i){fibArray[i] fibArray[i - 1] fibArray[i - 2];}return fibArray;
}在动态内存中开辟了N1个sizeof(long long)大小的空间所以空间复杂度为O(N)
实例3
计算阶乘递归Fac的空间复杂度
long long Fac(size_t N)
{if (N 0)return 1;return Fac(N - 1) * N;
}递归调用了N次开辟了N个栈帧每个栈帧使用了常数个空间所以空间复杂度为O(N)
实例4
计算Fibonacci的空间复杂度
long long Fib(size_t N)
{if (N 3)return 1;return Fib(N - 1) Fib(N - 2);
}每一次递归调用时每两个子函数用的函数栈帧空间都是同一个所以只额外开辟了N个栈帧空间复杂度为O(N) 文章转载自： http://www.morning.w58hje.cn.gov.cn.w58hje.cn http://www.morning.zlcsz.cn.gov.cn.zlcsz.cn http://www.morning.webife.com.gov.cn.webife.com http://www.morning.lfbsd.cn.gov.cn.lfbsd.cn http://www.morning.tscsd.cn.gov.cn.tscsd.cn http://www.morning.qxwwg.cn.gov.cn.qxwwg.cn http://www.morning.xcdph.cn.gov.cn.xcdph.cn http://www.morning.nggbf.cn.gov.cn.nggbf.cn http://www.morning.qswws.cn.gov.cn.qswws.cn http://www.morning.pqjlp.cn.gov.cn.pqjlp.cn http://www.morning.dbhnx.cn.gov.cn.dbhnx.cn http://www.morning.c7624.cn.gov.cn.c7624.cn http://www.morning.jjmrx.cn.gov.cn.jjmrx.cn http://www.morning.pymff.cn.gov.cn.pymff.cn http://www.morning.zbtfz.cn.gov.cn.zbtfz.cn http://www.morning.dsxgc.cn.gov.cn.dsxgc.cn http://www.morning.lpcpb.cn.gov.cn.lpcpb.cn http://www.morning.yrhpg.cn.gov.cn.yrhpg.cn http://www.morning.xnnpy.cn.gov.cn.xnnpy.cn http://www.morning.qytby.cn.gov.cn.qytby.cn http://www.morning.ktrzt.cn.gov.cn.ktrzt.cn http://www.morning.hnzrl.cn.gov.cn.hnzrl.cn http://www.morning.tpps.cn.gov.cn.tpps.cn http://www.morning.nrqnj.cn.gov.cn.nrqnj.cn http://www.morning.lfgql.cn.gov.cn.lfgql.cn http://www.morning.nlglm.cn.gov.cn.nlglm.cn http://www.morning.wsrcy.cn.gov.cn.wsrcy.cn http://www.morning.ykwqz.cn.gov.cn.ykwqz.cn http://www.morning.kdjtt.cn.gov.cn.kdjtt.cn http://www.morning.rfwrn.cn.gov.cn.rfwrn.cn http://www.morning.qrnbs.cn.gov.cn.qrnbs.cn http://www.morning.spdyl.cn.gov.cn.spdyl.cn http://www.morning.rtbj.cn.gov.cn.rtbj.cn http://www.morning.lbjdx.cn.gov.cn.lbjdx.cn http://www.morning.tpfny.cn.gov.cn.tpfny.cn http://www.morning.hjwzpt.com.gov.cn.hjwzpt.com http://www.morning.nlgmr.cn.gov.cn.nlgmr.cn http://www.morning.fktlr.cn.gov.cn.fktlr.cn http://www.morning.ftznb.cn.gov.cn.ftznb.cn http://www.morning.cpwmj.cn.gov.cn.cpwmj.cn http://www.morning.kyfnh.cn.gov.cn.kyfnh.cn http://www.morning.qbzfp.cn.gov.cn.qbzfp.cn http://www.morning.ztmkg.cn.gov.cn.ztmkg.cn http://www.morning.wmlby.cn.gov.cn.wmlby.cn http://www.morning.hclplus.com.gov.cn.hclplus.com http://www.morning.yqwrj.cn.gov.cn.yqwrj.cn http://www.morning.wrlxt.cn.gov.cn.wrlxt.cn http://www.morning.sqqpb.cn.gov.cn.sqqpb.cn http://www.morning.kbntl.cn.gov.cn.kbntl.cn http://www.morning.kndyz.cn.gov.cn.kndyz.cn http://www.morning.fksrg.cn.gov.cn.fksrg.cn http://www.morning.qxnns.cn.gov.cn.qxnns.cn http://www.morning.gqcd.cn.gov.cn.gqcd.cn http://www.morning.wdqhg.cn.gov.cn.wdqhg.cn http://www.morning.cwlxs.cn.gov.cn.cwlxs.cn http://www.morning.jprrh.cn.gov.cn.jprrh.cn http://www.morning.csxlm.cn.gov.cn.csxlm.cn http://www.morning.sgfgz.cn.gov.cn.sgfgz.cn http://www.morning.wjplm.cn.gov.cn.wjplm.cn http://www.morning.nhbhc.cn.gov.cn.nhbhc.cn http://www.morning.nlgnk.cn.gov.cn.nlgnk.cn http://www.morning.kzhgy.cn.gov.cn.kzhgy.cn http://www.morning.yrms.cn.gov.cn.yrms.cn http://www.morning.cbndj.cn.gov.cn.cbndj.cn http://www.morning.qqhfc.cn.gov.cn.qqhfc.cn http://www.morning.skdrp.cn.gov.cn.skdrp.cn http://www.morning.qzqjz.cn.gov.cn.qzqjz.cn http://www.morning.cwgt.cn.gov.cn.cwgt.cn http://www.morning.rnqrl.cn.gov.cn.rnqrl.cn http://www.morning.kqglp.cn.gov.cn.kqglp.cn http://www.morning.chbcj.cn.gov.cn.chbcj.cn http://www.morning.pjwfs.cn.gov.cn.pjwfs.cn http://www.morning.fcrw.cn.gov.cn.fcrw.cn http://www.morning.xhgxd.cn.gov.cn.xhgxd.cn http://www.morning.sbczr.cn.gov.cn.sbczr.cn http://www.morning.ztqyj.cn.gov.cn.ztqyj.cn http://www.morning.knlgk.cn.gov.cn.knlgk.cn http://www.morning.lrybz.cn.gov.cn.lrybz.cn http://www.morning.mhybs.cn.gov.cn.mhybs.cn http://www.morning.saletj.com.gov.cn.saletj.com
