Problem Solving with Algorithms

文章背景

常常会想这么一件事情，就是实现一个功能可能有很多种不同的方法，那么不同的方法效率都是相同的吗？不同的实现方法我们是否可以进行比较说某方法比另一个方法好呢？又该如何进行比较呢？

• 本周我在学习《Problem Solving with Algorithms and Data Structures using Python¶》这本书（quora（知乎就是模仿它）上好多大神推荐这本），实体书很贵，但是这个作者写了一个这本书的网站，完全免费，还能交互学习，实在是良心作者。本来有点怕我这点渣英语水平能不能看懂这本书，事实上是我多虑了。个人还是比较推荐看原版书，因为语言这个东西，一经过翻译，完全就不是一个味道了（翻译大神作品除外）。附上本书在线地址：Problem Solving with Algorithms and Data Structures using Python
• 目前的进度是一天看一章，预计一周看完，为了巩固知识，所以写这篇文章，也顺便分享下所学 for 那些不喜欢看英文书的小伙伴

目标

    + 1 理解为什么算法分析那么重要
+ 2 能够使用“Big-O”来描述程序执行时间
+ 3 理解同样的操作在Python 列表和字典 (lists and dictionaries)中的执行时间
+ 4了解Python数据的实现如何影响算法分析
+ 学会如何衡量简单的Python程序

什么是算法分析？

• 一种很常见的情况就是当一个人拿着他的程序跟另一个人的实现了同样功能的程序做对比时，到底哪个程序要优于另一个呢？
• 为了解答这个问题，我们需要记住程序与底层程序之间存在着一个重要的区别，就像我们之前谈到过的，算法是解决问题的一个通用的，循序渐进的指令列表，它是任何实例解决问题的一种方法。例如，我们给定一个输入，该算法产生我们期望的结果。一个程序，换个方面来说，就是一种编码成某种语言的算法。有可能很多程序使用着同样的算法，取决于程序员和程序员正在使用的编程语言。
• 为了进一步探讨这种差异，思考下以下代码：

   def sumOfN(n):
      theSum = 0
      for i in range(1,n+1):
          theSum = theSum + i

      return theSum

   print(sumOfN(10))

• 这个函数解决一个很常见的问题，计算前n个整数的和。这个算法的做法是先初始化一个值为0的名为theSum的变量，然后通过迭代每一个整数加到这个变量上去。
• 然后我们来看另一种实现方式，请看以下代码：

    def foo(tom):
        fred = 0
        for bill in range(1,tom+1):
           barney = bill
           fred = fred + barney

        return fred

    print(foo(10))

• 是不是看起来很像，几乎没什么区别。

• 我们之前提出的问题是，很相似的两个实现方式，其中一种是不是要比另一种好呢？函数sumOfN肯定要比foo好如果不考虑可读性的话。

• 算法分析涉及根据每个算法使用的计算资源量比较算法。我们希望能够考虑两种算法，并说其中一种比另一种更好，因为它在使用这些资源时效率更高，或者可能是因为它只使用较少的资源。从这个角度看，上面的两个函数看起来非常相似。它们都使用基本相同的算法来解决求和问题。

• 那么我们来看看它们的运行时间是否存在差异呢？我们使用python自带的time模块来检测运行时间，做法如下：

  import time
  
  def sumOfN2(n):
     start = time.time()
  
     theSum = 0
     for i in range(1,n+1):
        theSum = theSum + i
  
     end = time.time()
  
     return theSum,end-start
  

• 另一个函数同理

• 我们来测试下前10000求和时间

   
   >>>for i in range(5):
          print("Sum is %d required %10.7f seconds"%sumOfN(10000))
   Sum is 50005000 required  0.0018950 seconds
   Sum is 50005000 required  0.0018620 seconds
   Sum is 50005000 required  0.0019171 seconds
   Sum is 50005000 required  0.0019162 seconds
   Sum is 50005000 required  0.0019360 seconds

• 我们把前10000改成100000

    
    >>>for i in range(5):
           print("Sum is %d required %10.7f seconds"%sumOfN(100000))
    Sum is 5000050000 required  0.0199420 seconds
    Sum is 5000050000 required  0.0180972 seconds
    Sum is 5000050000 required  0.0194821 seconds
    Sum is 5000050000 required  0.0178988 seconds
    Sum is 5000050000 required  0.0188949 seconds
    >>>

• 我们可以看到数量每次多10倍，时间也是多10倍
• 我们再来试一下另一种算法

   def sumOfN3(n):
      return (n*(n+1))/2

   print(sumOfN3(10))

• 数学稍微懂点都知道这个公式吧- -，我们再来看下运行时间

• 我们用不同的值测试（10,000, 100,000, 1,000,000, 10,000,000, 100,000,000）

  
  Sum is 50005000 required 0.00000095 seconds
  Sum is 5000050000 required 0.00000191 seconds
  Sum is 500000500000 required 0.00000095 seconds
  Sum is 50000005000000 required 0.00000095 seconds
  Sum is 5000000050000000 required 0.00000119 seconds
  

• 我们可以发现，随着数量的增加，对运行时间几乎没有影响。

• 这就是算法的魅力吧

Big-O 符号

• 一张图概括

  
  Big-O.png

Python列表时间复杂度

• 看图

image.png

• 这里可能会对pop()方法有疑问

其实因为python列表如果从前面删掉一个的话它会把后面部分整体的位置往左移动一个位置，方便索引吧，我是这么理解的。。。

Python字典时间复杂度

image.png

总结

• 算法分析真的很重要，不同的算法带来的结果有时候差异很大
• Big-O 决定于位数最高的那个，就像大学微积分，比方说2n2+2 复杂度就是f（n2） 2代表平方