网络营销就是网站营销,怎样搞网络营销,微信开发者工具的介绍,flash+xml网站模板细化时间复杂度分析 代码千千万#xff0c;有些代码逻辑会很复杂#xff0c;所以为了更细化的分析算法的复杂度#xff0c;再复杂度分析方面引入了4个知识点#xff1a; 1.最好情况时间复杂度#xff08;best case time complexity#xff09;。 2.最坏情况时间复杂度有些代码逻辑会很复杂所以为了更细化的分析算法的复杂度再复杂度分析方面引入了4个知识点 1.最好情况时间复杂度best case time complexity。 2.最坏情况时间复杂度worst case time complexity。 3.平均情况时间复杂度average case time complexity。 4.均摊时间复杂度amortized time complexity。 复杂度分析 示例如下(限定条件:0n且0x且n和x为整数) 1 public int Function(int n, int x)2 {3 int sum 0;4 for (int i 1; i n; i)5 {6 if (i x)7 break;8 sum i;9 }
10 return sum;
11 }
12 /*
13 * 作者Jonins
14 * 出处http://www.cnblogs.com/jonins/
15 */ 这段代码逻辑非常简单再此不描述。需要重点分析的是循环这一段代码这段代码根据x值的不同时间复杂度也有区别 1.当xn时此代码的时间复杂度是O(n)。 2.当1xn时时间复杂度是一个我们不确定的值取决于x的值。 3.当x1时时间复杂度是O(1)。 这段代码在不同情况下其时间复杂度是不一样的。所以为了描述代码在不同情况下的不同时间复杂度我们引入了最好、最坏、平均时间复杂度。 最好情况时间复杂度 最好情况时间复杂度表示在最理想的情况下执行这段代码的时间复杂度。 上述示例就是当x1的时候循环的第一个判断就跳出这个时候对应的时间复杂度就是最好情况时间复杂度。 最坏情况时间复杂度 最坏情况时间复杂度表示在最糟糕的情况下执行这段代码的时间复杂度。 上述示例就是nx的时候我们要把整个循环执行一遍这个时候对应的时间复杂度就是最坏情况时间复杂度。 平均情况时间复杂度 最好和最好情况是极端情况发生的概率并不大。为了更有效的表示平均情况下的时间复杂度引入另一个概念平均情况时间复杂度。 分析上面的示例代码判断x在循环中出现的位置有n1种情况1xn 和nx。 我们将所有情况下代码执行的次数累加起来123....nn然后再除以所有情况数量n1就可以得到需要遍历次数的平均值。 平均情况复杂度为 $ \frac{((123...n)n)}{(n1)}\frac{n(n3)}{2(n1)} $ 推导过程 $ \because 123...nn(n-1)(n-2)...1 $ $ \therefore (123...n)\frac{n(1n)}{2} $ $ \therefore (123...n)n \frac{n(3n)}{2} $ 大O表示法会省略系数、低阶、常量所以平均情况时间复杂度是O(n)。 但是这个平均复杂度没有考虑各自情况的发生概率这里的n1个情况它们的发生概率是不一样的所以还需要引入各自情况发生的概率再具体分析。 x要么在1~n中要么不在1~n中所以它们的概率都是$\frac{1}{2}$。 同时数据在1~n中各个位置的概率都是一样的为$\frac{1}{n}$。根据概率乘法法则x在1~n中任意位置的概率是$\frac{1}{2n}$。 因此在前面推导过程的基础上我们把每种情况发生的概率考虑进去那么平均情况时间复杂度的计算过程变成 考虑概率的平均情况复杂度为 $(1\frac{1}{2n}2\frac{1}{2n}3\frac{1}{2n}...n\frac{1}{2n})n\frac{1}{2}\frac{3n1}{4}$ 推导过程 $\because (123...n)\frac{n(1n)}{2}$ $\therefore (1\frac{1}{2n}2\frac{1}{2n}3\frac{1}{2n}...n\frac{1}{2n})\frac{1}{2n}(123...n)\frac{1}{2n}*\frac{n(1n)}{2} \frac{1n}{4}$ $\therefore (1\frac{1}{2n}2\frac{1}{2n}3\frac{1}{2n}...n\frac{1}{2n})n\frac{1}{2}\frac{1n}{4} n\frac{1}{2}\frac{3n1}{4}$ 这就是概率论中的加权平均值也叫做期望值所以平均时间复杂度全称叫加权平均时间复杂度或者期望时间复杂度。 引入概率之后平均复杂度变为O($\frac{3n1}{4}$)忽略系数及常量后最终得到加权平均时间复杂度为O(n)。 注意 多数情况下我们不需要区分最好、最坏、平均情况时间复杂度。只有同一块代码在不同情况下时间复杂度有量级差距我们才会区分3种情况为的是更有效的描述代码的时间复杂度。 均摊情况时间复杂度 均摊复杂度是一个更加高级的概念它是一种特殊的情况应用的场景也更加特殊和有限。 对应的分析方式称为摊还分析或平摊分析。 示例如下限定条件0xn且0n且n,x为整数 1 int n;2 int Function2(int x)3 {4 int count 0;5 if (n x)6 {7 for (int i 0; i n; i)8 {9 count i;
10 }
11 }
12 else
13 count x;
14 return count;
15 }
16 /* 作者Jonins
17 * 出处http://www.cnblogs.com/jonins/
18 */ 分析上述案例的时间复杂度 最理想情况下x!n只执行一次赋值即可推出所以最好时间复杂度为O(1)。 最坏的情况下xn要执行一次循环累加和的操作所以最好时间复杂度为O(n)。 平均的情况下因为限定条件0xnx在0~n中存在的位置可以分为n1种情况(0到n)。 当0xn时时间复杂度为O(1)。但是xn的时候是一个例外它的复杂度是O(n)。 而且这n1种情况发生的概率都是一样的为$\frac{1}{n1}$。所以根据加权平均的计算方法 平均时间复杂度为 $ (1\tfrac{1}{n1}1\tfrac{1}{n1}1\tfrac{1}{n1}...1\tfrac{1}{n1})n\tfrac{1}{n1} \tfrac{2n}{n1} $ 推导过程 $(1\tfrac{1}{n1}1\tfrac{1}{n1}1\tfrac{1}{n1}...1\tfrac{1}{n1})n\tfrac{1}{n1}$ $n\tfrac{1}{n1}n\tfrac{1}{n1}$ $\tfrac{2n}{n1}$ 当省略系数及常量后平均时间复杂度为O(1)。 摊还分析法 分析上述示例的平均复杂度分析并不需要如此复杂无需引入概率论的知识。 因为通过分析可以看出上述示例代码复杂度大多数为O(1)极端情况下复杂度才较高为O(n)。同时复杂度遵循一定的规律一般为1个O(n)和n个O(1)。针对这样一种特殊场景使用更简单的分析方法摊还分析法。 通过摊还分析法得到的时间复杂度为均摊时间复杂度。 大致思路每一次O(n)都会跟着n次O(1)所以把耗时多的复杂度均摊到耗时低的复杂度。得到的均摊时间复杂度为O(1)。 应用场景均摊时间复杂度和摊还分析应用场景较为特殊对一个数据进行连续操作大部分情况下时间复杂度都很低只有个别情况下时间复杂度较高。而这组操作其存在前后连贯的时序关系。 这个时候我们将这一组操作放在一起分析将高复杂度均摊到其余低复杂度上所以一般均摊时间复杂度就等于最好情况时间复杂度。 注意均摊时间复杂度是一种特殊的平均复杂度特殊应用场景下使用掌握分析方式即可。 转载于:https://www.cnblogs.com/jonins/p/9956752.html
