算法效率分析
本帖最后由 天洑软件 于 2019-3-27 17:08 编辑算法是一系列解决问题的明确指令，对于一定符合规范的输入，能够在有限时间内获得要求的输出。从实际问题的提出到设计合适的算法再到正确性的分析以及算法效率的分析，最后为算法编写代码，一步步得到问题的解决方案。
http://www.njtf.cn/ueditor/net/upload/2017-06-29/c7635c09-d21c-45bf-b4bb-2421027f824d.png图1.算法的概念
http://www.njtf.cn/ueditor/net/upload/2017-06-29/cbd10835-aee5-4df7-8c5a-943cae1029ec.png图2.算法设计分析过程
对算法效率的分析，需要指出有两种算法效率：时间效率和空间效率，分指算法运行速度和需要的额外空间。由于技术革新，对于大多数问题，速度上效率的提高远大于空间上的提高。在研究算法效率上提出一般性框架。定义1：如果存在正常数c和http://www.njtf.cn/ueditor/net/upload/2017-06-29/e2376e90-3b50-4a26-832f-05cefb0dad1f.png使得当http://www.njtf.cn/ueditor/net/upload/2017-06-29/cea8a616-5205-478f-8eab-0e0dcd8599d4.png时http://www.njtf.cn/ueditor/net/upload/2017-06-29/c7f35b8d-2b14-456a-80fc-e6f6564128f2.png，则记为http://www.njtf.cn/ueditor/net/upload/2017-06-29/f70ae7ab-03af-431f-a0a7-6d62bb610817.png。
定义2：如果存在正常数c和http://www.njtf.cn/ueditor/net/upload/2017-06-29/9af9f3b4-a955-4298-aca1-2cd8ffb62418.png使得当http://www.njtf.cn/ueditor/net/upload/2017-06-29/741f2606-9500-4b0a-b7f1-c0da07bf18d4.png时http://www.njtf.cn/ueditor/net/upload/2017-06-29/f6ea3689-c5b7-4920-bab2-11a90bcb6077.png，则记为http://www.njtf.cn/ueditor/net/upload/2017-06-29/9272da14-312a-4f7e-ba76-1bb070c73cb6.png。定义3：http://www.njtf.cn/ueditor/net/upload/2017-06-29/7ea50a92-f616-4f2d-9491-12a0ab109849.png当且仅当http://www.njtf.cn/ueditor/net/upload/2017-06-29/6bb44be7-8219-44d4-9cb8-ecbc084e6203.png且http://www.njtf.cn/ueditor/net/upload/2017-06-29/2aea5c47-f234-44e7-ba8e-b7cd9cb24d8e.png。定义4：如果http://www.njtf.cn/ueditor/net/upload/2017-06-29/0d60ad8b-2ef6-43bf-a41f-63ea68bbccce.png且http://www.njtf.cn/ueditor/net/upload/2017-06-29/caab36a3-6000-4a9a-b827-c3398ccc2b6d.png，则http://www.njtf.cn/ueditor/net/upload/2017-06-29/fe9cbc5b-0336-46cb-afb7-36da651f01c6.png。定义的目的实在函数之间建立相对的级别。可直观的理解为http://www.njtf.cn/ueditor/net/upload/2017-06-29/bc3c1472-1586-450e-89ef-b73326f213ee.png增长率小于等于http://www.njtf.cn/ueditor/net/upload/2017-06-29/6c13b490-64d0-4139-99e8-6b5726c08e8d.png，http://www.njtf.cn/ueditor/net/upload/2017-06-29/980aa715-2b55-490e-a3ed-516896c8a79f.png增长率大于等于http://www.njtf.cn/ueditor/net/upload/2017-06-29/abed107a-7a44-417a-843b-64a48f0f14ab.png，http://www.njtf.cn/ueditor/net/upload/2017-06-29/44c31de3-9106-43a9-b088-5803f273e082.png增长率等于http://www.njtf.cn/ueditor/net/upload/2017-06-29/2342ebd4-f824-4cff-ac17-05f2f1159464.png，http://www.njtf.cn/ueditor/net/upload/2017-06-29/84d105f8-576e-40f8-9f8f-a03d7d23bd4e.png增长率小于http://www.njtf.cn/ueditor/net/upload/2017-06-29/d9fa7d5e-c64f-47b1-8719-bd29654e24a9.png。
法则1：如果http://www.njtf.cn/ueditor/net/upload/2017-06-29/d57d1fd7-597b-40ec-8a4e-82cbea5b9bb8.png且http://www.njtf.cn/ueditor/net/upload/2017-06-29/11365342-371f-471c-bafb-c35f4c5bc0ca.png，那么（a）http://www.njtf.cn/ueditor/net/upload/2017-06-29/723a226e-9cf9-49b3-8026-df55036c081c.png（b）http://www.njtf.cn/ueditor/net/upload/2017-06-29/57a87b86-0ef6-4af2-890b-39447bcf82e5.png法则2：如果http://www.njtf.cn/ueditor/net/upload/2017-06-29/5d6b37ec-a9bb-4b98-aa20-4d71f43b1124.png是k次多项式，则http://www.njtf.cn/ueditor/net/upload/2017-06-29/83587b48-8095-45ff-9c03-d620a3b98ec0.png法则3：对任意常数k，http://www.njtf.cn/ueditor/net/upload/2017-06-29/0cd68139-b423-45ec-9877-48330a484136.png 下面以最大子序列和问题的四种解决方法来分析算法的效率问题。最大子序列和：给定整数http://www.njtf.cn/ueditor/net/upload/2017-06-29/ed167c56-fa3a-4967-8adf-677df26a0f29.png（可能含负数），求http://www.njtf.cn/ueditor/net/upload/2017-06-29/50e47246-87e6-4aff-92d2-3bc8bb308eda.png最大值（若所有整数为负，则最大子序列和为0）
算法1234
时间http://www.njtf.cn/ueditor/net/upload/2017-06-29/18b665ec-002e-4cc0-a833-fc080609f4de.pnghttp://www.njtf.cn/ueditor/net/upload/2017-06-29/a21981e8-6cfa-4ee4-bc8f-7514bcc3c93d.pnghttp://www.njtf.cn/ueditor/net/upload/2017-06-29/bf03ddd0-526d-46d3-b8ee-90f53d727cd0.pnghttp://www.njtf.cn/ueditor/net/upload/2017-06-29/da175a89-2825-414e-9054-c4a5d4d103d5.png
输入大小/mN=100.001030.000450.000660.00034
N=1000.470150.011120.004860.00063
N=1000448.771.12330.058430.00333
N=10000NA111.130.686310.03042
N=100000NANA8.01130.29832
http://www.njtf.cn/ueditor/net/upload/2017-06-29/8decfa25-b5cb-4de9-9b37-5341ac1b1b15.png
http://www.njtf.cn/ueditor/net/upload/2017-06-29/52041bb3-fb03-48cd-80e6-bf969b470cb4.png
方法一、穷举尝试所有可能，含有3重for循环。第一循环大小为N，第二循环大小为http://www.njtf.cn/ueditor/net/upload/2017-06-29/2cc46560-28bb-4917-a570-018a5d78aafd.png，第三循环大小为http://www.njtf.cn/ueditor/net/upload/2017-06-29/5afa95d2-3b7b-489b-ad6c-091d5f812b65.png。考虑最差时间效率，第二循环第三循环大小均为N。总数为http://www.njtf.cn/ueditor/net/upload/2017-06-29/07416667-fc82-42d1-8c12-046880da4ecc.png。可精确分析，第三循环时间http://www.njtf.cn/ueditor/net/upload/2017-06-29/676bd205-c173-4da3-84a6-5968117e6c29.png
int MaxSubsequenceSum(const int A[], int N){ int ThisSum, MaxSum, i, j, k; MaxSum = 0; for (i = 0; i < N;i++) for (j = i; j < N; j++) { ThisSum = 0; for (k = i; k <= j; k++) ThisSum += A; if (ThisSum > MaxSum) MaxSum = ThisSum; } return MaxSum;}
http://www.njtf.cn/ueditor/net/upload/2017-06-29/2fdf6312-f13c-41d7-9eea-676a808919c5.png
方法二、在方法一的基础上去掉三重循环，复杂度降为http://www.njtf.cn/ueditor/net/upload/2017-06-29/6942acd5-fe7d-4180-a76b-c2d6da0b687c.png
int MaxSubsequenceSum(const int A[], int N){ int ThisSum, MaxSum, i, j, k; MaxSum = 0; for (i = 0; i < N; i++) { ThisSum = 0; for (j = i; j < N; j++) { ThisSum += A; if (ThisSum > MaxSum) MaxSum = ThisSum; } } return MaxSum;}
方法三、使用一种递归的方法，使复杂度降为http://www.njtf.cn/ueditor/net/upload/2017-06-29/4d9b64af-4376-41b9-9735-19aeba2c0a0b.png。当问题无法找到http://www.njtf.cn/ueditor/net/upload/2017-06-29/e0962348-0497-4c93-ba6f-f9ec98bc5c08.png复杂度的线性解法前，该方法很好的体现递归的强力。方法使用“分治”策略。将问题“分割”成两个大致相等的子问题，再将两个子问题的解合并，再做少量工作使问题解决。假设测试序列：
前半部后半部
4-35-2-126-2
1前半部最大子序列和为6（http://www.njtf.cn/ueditor/net/upload/2017-06-29/53a7bc24-74ed-4b30-885d-becd2895e1e6.png），后半部最大子序列和为8（http://www.njtf.cn/ueditor/net/upload/2017-06-29/7e49f23b-3d2f-4941-82b8-3f0b012fa0d6.png）2前半部包含最后元素最大和为4（http://www.njtf.cn/ueditor/net/upload/2017-06-29/a6c6d76a-29f9-4c91-b170-28172d158893.png），后半部第一元素最大和为7（http://www.njtf.cn/ueditor/net/upload/2017-06-29/e19d638f-7b35-4521-b570-ed29fbaebfdb.png）3两部分最大和11（http://www.njtf.cn/ueditor/net/upload/2017-06-29/d751aa7b-979f-4632-bc32-7b46221af032.png）算法3比前两种需要更多代码量，但在运行时间上，特别是大数据量的运算时间，会比前两种方法节省更多时间。方法四、极为简洁而且更加的有效。打破了第二循环和第三循环，使运行时间变为线性。
int MaxSubsequenceSum(const int A[], int N){ int ThisSum, MaxSum, j; MaxSum = ThisSum = 0; for (j = 0; j < N; j++) { ThisSum += A; if (ThisSum > MaxSum) MaxSum = ThisSum; else if (ThisSum < 0) ThisSum = 0;} return MaxSum;}
在实际的代码编写中，对算法复杂度进行估算，可以更加有计划性的进行算法改进。提高时间效率。
关注公众号“天洑CAE技术源”了解更多相关资讯
http://forum.simwe.com/data/attachment/forum/201903/27/170148yd0wexhz999j9xd0.jpg
页:
[1]