第二章 Big O notation 进阶课程

第二章 

Big O notation 进阶课程

在这一章中，我们将会了解到算法的基础----Counting primitive operation，什么是primitive operation：

The following are all primitive operations:

1. Assigning a value to a variable

2. Calling another algorithm (function)

3. Performing an arithmetic operation (adding, etc)

4. Indexing into an array

5. Comparing two values (includes all logical and relational

6. operators)

7. Following (dereferencing) an object reference (pointer)

8. Returning from a method (function, procedure)

举一个例子：

currentMax <-A[0]      2 ops
i <-1                                    1 op
while (i < n) do      1 op
if ( currentMax < A[i] )      2 ops
then currentMax Ω A[i]        2 ops
i <- i + 1                              2 ops
done
return currentMax               1 op

Loop Body:

Single loop body iteration: 5 or 7 operations

Loop body repeated n -1 times.

So: between 5(n -1) and 7(n-1) operations, when n > 1
Best case: t = 2 + 1 + 5(n - 1) + 1 = 5n -1
Worst case: t = 2 + 1 + 7(n - 1) + 1 = 7n -3

举一个我们学校的例子吧

在这里我们可以看到在这两个方程中，想得到big O 的话，我们需要将内外两个loop的big O相乘

 而第一个例子会变成从一到n-1的累加，而结果是n(n-1)/2

在这里我放上一个讲解比较优秀的网站链接，大家如果感兴趣可以看一下的：

http://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/

另外给大家几道试题做，大家试试看，下期我会公布答案，并且详细的解答。

第二章 Big O notation 进阶课程

原文：http://blog.csdn.net/u013152895/article/details/44116051