每日彙整: 2017-03-16

樹莓派、樹莓派之學習、樹莓派之教育

時間序列︰生成函數‧漸近展開︰無限大等級 I

如何創造一根尺，用以分析演算法

Analysis of algorithms

In computer science, the analysis of algorithms is the determination of the amount of resources (such as time and storage) necessary to execute them. Most algorithms are designed to work with inputs of arbitrary length. Usually, the efficiency or running time of an algorithm is stated as a function relating the input length to the number of steps (time complexity) or storage locations (space complexity).

The term “analysis of algorithms” was coined by Donald Knuth.[1] Algorithm analysis is an important part of a broader computational complexity theory, which provides theoretical estimates for the resources needed by any algorithm which solves a given computational problem. These estimates provide an insight into reasonable directions of search for efficient algorithms.

In theoretical analysis of algorithms it is common to estimate their complexity in the asymptotic sense, i.e., to estimate the complexity function for arbitrarily large input. Big O notation, Big-omega notation and Big-theta notation are used to this end. For instance, binary search is said to run in a number of steps proportional to the logarithm of the length of the sorted list being searched, or in O(log(n)), colloquially “in logarithmic time“. Usually asymptotic estimates are used because different implementations of the same algorithm may differ in efficiency. However the efficiencies of any two “reasonable” implementations of a given algorithm are related by a constant multiplicative factor called a hidden constant.

Exact (not asymptotic) measures of efficiency can sometimes be computed but they usually require certain assumptions concerning the particular implementation of the algorithm, called model of computation. A model of computation may be defined in terms of an abstract computer, e.g., Turing machine, and/or by postulating that certain operations are executed in unit time. For example, if the sorted list to which we apply binary search has n elements, and we can guarantee that each lookup of an element in the list can be done in unit time, then at most log2 n + 1 time units are needed to return an answer.

Graphs of number of operations, N vs input size, n for common complexities, assuming a coefficient of 1

 

，度量它的『時間』、『空間』之複雜性？

即使對一個簡單的演算法，都顯得困難重重！

運行時間複雜度的分析

分析一個算法的最壞運行時間複雜度時，人們常常作出一些簡化問題的假設，並分析該算法的結構。以下是一個例子：

1    从输入值中获取一个正数
2    if n > 10
3        print "耗时可能较长，请稍候……"
4    for i = 1 to n
5        for j = 1 to i
6            print i * j
7    print "完成！"

一台給定的電腦執行每一條指令的時間是確定[8]的，並可以用 DTIME 描述。 假設第 1 步操作需時 T1，第 2 步操作需時 T2，如此類推。

步驟 1、2、7 只會運行一次。應當假設在最壞情況下，步驟 3 也會運行。步驟 1 至 3 和步驟 7 的總運行時間是：

T_{1}+T_{2}+T_{3}+T_{7}

步驟 4、5、6 中的循環更為複雜。步驟 4 中的最外層循環會執行 (n + 1) 次（需要一次執行來結束 for 循環，因此是 (n + 1) 次而非 n 次），因此會消耗 T4 × (n + 1) 單位時間。內層循環則由 i 的值控制，它會從 1 疊代到 n。 第一次執行外層循環時，j 從 1 疊代到 1，因此內層循環也執行一次，總共耗時 T6 時間。以及內層循環的判斷語句消耗 3T5 時間。

所以，內層循環的總共耗時可以用一個等差級數表示：

T_{6}+2T_{6}+3T_{6}+\cdots +(n-1)T_{6}+nT_{6}

上式可被因式分解[9]為：

 T_{6}\left[1+2+3+\cdots +(n-1)+n\right]=T_{6}\left[{\frac {1}{2}}(n^{2}+n)\right]

類似地，可以分析內層循環的判斷語句：

2T_{5}+3T_{5}+4T_{5}+\cdots +(n-1)T_{5}+nT_{5}+(n+1)T_{5}
=T_{5}+2T_{5}+3T_{5}+4T_{5}+\cdots +(n-1)T_{5}+nT_{5}+(n+1)T_{5}-T_{5}

上式可被分解為：

T_{5}\left[1+2+3+\cdots +(n-1)+n+(n+1)\right]-T_{5}
=\left[{\frac {1}{2}}(n^{2}+n)\right]T_{5}+(n+1)T_{5}-T_{5}
  =T_{5}\left[{\frac {1}{2}}(n^{2}+n)\right]+nT_{5}
  =\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}

因此該算法的總運行時間為：

f(n)=T_{1}+T_{2}+T_{3}+T_{7}+(n+1)T_{4}+\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}

改寫一下：

  f(n)=\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}

通常情況下，一個函數的最高次項對它的增長率起到主導作用。在此例里，n² 是最高次項，所以有結論  f(n)=O(n^{2})。

嚴格證明如下：證明 \left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},\ n\geq n_{0}

\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}

\leq (n^{2}+n)T_{6}+(n^{2}+3n)T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\ (n\geq 0)

令 k 為一個常數，其大於從 T1 到 T7 所有的數。

T_{6}(n^{2}+n)+T_{5}(n^{2}+3n)+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq k(n^{2}+n)+k(n^{2}+3n)+kn+5k

=2kn^{2}+5kn+5k\leq 2kn^{2}+5kn^{2}+5kn^{2}\,(n\geq 1)=12kn^{2}

因此有

\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},n\geq n_{0}，其中  c=12k,n_{0}=1

還可以假定所有步驟全部消耗相同的時間，它的值比 T1 到 T7 中任意一個都大。這樣的話，這個算法的運行時間就可以這樣來分析：[10]

4+\sum _{{i=1}}^{n}i\leq 4+\sum _{{i=1}}^{n}n=4+n^{2}\leq 5n^{2}\,(n\geq 1)=O(n^{2}).

 

還得知道 O(n) 比 O(n^2) 好，因為 \lim \limits_{n \to \infty} \frac{n}{n^2} \to 0 。那麼 O(log(n)) 比 n 好嗎？？於是我們需要計算 \frac{\infty}{\infty} 的辦法！！

L’Hôpital’s rule

In mathematics, and more specifically in calculus, L’Hôpital’s rule or L’Hospital’s rule (French: [lopital]) uses derivatives to help evaluate limits involving indeterminate forms. Application (or repeated application) of the rule often converts an indeterminate form to an expression that can be evaluated by substitution, allowing easier evaluation of the limit. The rule is named after the 17th-century French mathematician Guillaume de l’Hôpital. Although the contribution of the rule is often attributed to L’Hôpital, the theorem was first introduced to L’Hôpital in 1694 by the Swiss mathematician Johann Bernoulli.

L’Hôpital’s rule states that for functions f and g which are differentiable on an open interval I except possibly at a point c contained in I, if

  {\displaystyle \lim _{x\to c}f(x)=\lim _{x\to c}g(x)=0{\text{ or }}\pm \infty ,}
  {\displaystyle g'(x)\neq 0} for all x in I with x ≠ c, and
  \lim _{x\to c}{\frac {f'(x)}{g'(x)}} exists, then
  {\displaystyle \lim _{x\to c}{\frac {f(x)}{g(x)}}=\lim _{x\to c}{\frac {f'(x)}{g'(x)}}.}

The differentiation of the numerator and denominator often simplifies the quotient or converts it to a limit that can be evaluated directly.

Example application of l’Hôpital’s rule to f(x)=sin(x) and g(x)=−0.5x: the function h(x) = f(x)/g(x) is undefined at x = 0, but can be completed to a continuous function on whole ℝ by defining h(0) = f′(0)/g′(0) = −2.

 

理解無限大實有『等級』。進而了解指數對數尺度的重要性。