图解算法系列笔记（一）

二分法查找

在有序的数组中，用二分法查找需要检查多少个元素

完整实现代码如下：（笔记都是Python语言实现）

  

   

    

     

    
    

     

      def binary_search(list,item):
     
    
   

    

     

    
    

     

          low=0
     
    
   

    

     

    
    

     

          high=len(list)-1
     
    
   

    

     

    
    

     
    while low<=high:
     
    
   

    

     

    
    

     

              mid=(low+high)/2
     
    
   

    

     

    
    

     

              guess=list[mid]
     
    
   

    

     

    
    

     
        if guess==item:
     
    
   

    

     

    
    

     
            return mid
     
    
   

    

     

    
    

     
        if guess>item:
     
    
   

    

     

    
    

     

                  high=mid-1
     
    
   

    

     

    
    

     
        else :
     
    
   

    

     

    
    

     

                  low=mid+1
     
    
   

    

     

    
    

     

      return None      #没有指定的元素
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      my_list=[1,3,5,7,9]
     
    
   

    

     

    
    

     

      print(binary_search(my_list,3)   #=>1 第二个位置的索引为1
     
    
   

    

     

    
    

     

      print(binary_search(my_list,-1)  #=>None 没有找到指定的元素
     
    
  
 

大O表示法

该算法指出了算法有多快。大O表示法指的并非以秒为单位的速度，而是比较操作数，指出算法运行时间的增速。大O算法一般运行时间都省略常数，+、-、乘除也都省略。
二分法使用大O表示法表示运行时间为O(log n)。
下面从快到慢的顺序列出了15种大O运行时间：
O(log n)，也叫对数时间，包括二分查找
O(n)，也叫线性时间，包括简单查找
O(n x logn)，快速排序法—速度较快的算法
O(n^2)，选择排序——一种速度较慢的算法
O(n!)，旅行商问题的解决方法——非常慢的算法

选择排序

数组：所有数组在内存中都是相连的（紧靠在一起）。如果·计算机预留内存不够，就得转移到其它内存去。一般计算机都会预留比较多的内存已让其它数组存进来，但是这也是对内存的一种浪费。
链表：链表的每一个元素都储存了下一个元素的地址，从而使一系列随机的内存地址串在一起。所以在链表添加元素很容易，只需将其放入内存，并将其地址储存在前一个元素中。
所以链表读取速度慢，但是插入速度快；数组插入速度慢。
下面是常见数组和链表操作的运行时间

| |数组 |链表 |
| 读取 | O(1) | O(n)|
| 插入 |O(n) |O(1) |
|删除 |O(n) |O(1) |
数组一般用的比较多，因为它支持随机访问和顺序访问；而链表只能顺序访问，因此经常说数组的读取速度很快。
示例代码：

  

   

    

     

    
    

     

      #查找最小值的函数
     
    
   

    

     

    
    

     

      def findSmalllest(arr):
     
    
   

    

     

    
    

     

          smallest=arr[0]    #储存最小的值
     
    
   

    

     

    
    

     

          smallest_index=0   #储存最小元素的索引
     
    
   

    

     

    
    

     
    for i in range(1,len(arr)):
     
    
   

    

     

    
    

     
        if arr[i]<smallest:
     
    
   

    

     

    
    

     

                  smallest=arr[i]
     
    
   

    

     

    
    

     

                  smallest_index=i
     
    
   

    

     

    
    

     
 #对数组进行排序
     
    
   

    

     

    
    

     
 def selectionSort(arr):
     
    
   

    

     

    
    

     

          newArr=[]
     
    
   

    

     

    
    

     
    for i in range(len(arr)):
     
    
   

    

     

    
    

     

              smallest=findSmallest(arr)
     
    
   

    

     

    
    

     

              newArr.append(arr.pop(smallest)
     
    
   

    

     

    
    

     
    return newArr
     
    
   

    

     

    
    

     
    
     
    
   

    

     

    
    

     
 print(selectionSort([5,3,6,2,10]))
     
    
  
 

递归

每个函数都有两部分：基线条件和递归条件。递归条件指的是函数调用自己，而基线条件指的是函数不再调用自己，从而避免形成无限循环。如下述伪代码所示：

  

   

    

     

    
    

     

      def countdown(i):
     
    
   

    

     

    
    

     

       print(i)
     
    
   

    

     

    
    

     

       if (i<=1):    //基线条件
     
    
   

    

     

    
    

     
      return 
     
    
   

    

     

    
    

     
    else:        //递归条件
     
    
   

    

     

    
    

     
      countdown(i-1)
     
    
  
 

快速排序

你有可能会遇到使用任何已知的算法都无法解决的问题，优秀的人一般都不会放弃，分而治之（D&C）【divide and conquer】是你学习的第一种通用的问题的解决方法。
提示：编写涉及数组的递归函数时，基线条件通常是数组为空或只包含一个元素。陷入困境时，请检查基线条件是不是这样的。
例如：请编写一个递归函数来计算列表包含的元素数。

  

   

    

     

    
    

     

      def count(list):
     
    
   

    

     

    
    

     
    if list==[]:
     
    
   

    

     

    
    

     
      return 0
     
    
   

    

     

    
    

     
    else:
     
    
   

    

     

    
    

     
      return 1+count(list[1:]) 
     
    
  
 

找出列表中最大的数字：

  

   

    

     

    
    

     

      def max(list):
     
    
   

    

     

    
    

     
    if len(list)==2:
     
    
   

    

     

    
    

     
      return list[0] if list[0]>list[1] else list[1]
     
    
   

    

     

    
    

     

          sub_max=max(list[1:])
     
    
   

    

     

    
    

     
    return list[0] if list[0]>sub_max else sub_max
     
    
  
 

C语言标准库中的函数qsort 实现的就是快速排序，快速排序也使用了D&C。
快速排序步骤
（1）选择一个基准值
（2）将数组分为两个子数组：小于基准值的元素和大于基准值的元素。
（3）对这两个数组进行快速排序【按步骤一来】
以此类推，对其它数组都进行快速排序


下面是快速排序的代码：

  

   

    

     

    
    

     

      def quicksort(array):
     
    
   

    

     

    
    

     
    if len(array) < 2:
     
    
   

    

     

    
    

     
      return array    //基线条件：为空或只包含一个元素的数组是有序的
     
    
   

    

     

    
    

     
    else:
     
    
   

    

     

    
    

     

            pivot = array[0]      //递归条件
     
    
   

    

     

    
    

     

            less = [i for i in array[1:] if i <= pivot     //由小于或等于基准值的元素组成的子数组
     
    
   

    

     

    
    

     

            greater = [i for i in array[1:] if i > pivot]   //由所有大于基准值的元素组成的子数组
     
    
   

    

     

    
    

     
      return quicksort(less) + [pivot] + quicksort(greater)
     
    
   

    

     

    
    

     

      print(quicksort([10,5,2,3]))
     
    
  
 

在大O表示法O(n)中，n实际上指的是这样的：c x n（其中C为固定的时间量）。通常不考虑这个常量，因为如果两种算法的大O运行时间不同，这种常量将无关紧要。如下面这个例子：
简单查找：10（毫秒）x n
二分查找：1（秒）x logn
如上述所示，你可能认为简单查找的速度要快于二分查找，然而实际上二分查找要速度快得多。所以常量根本没有什么影响。

在这实例中，层数为O(log n)用技术术语来说，调用栈的高度为O(log n)，而每层需要的时间为O(n)。因此整个算法需要的时间为O(n)xO(log n)=O(nlog n)。
在最糟的情况下，有O(n)层，因此该算法的运行时间为O(n)xO(n)=O(n^2)。

文章来源: blog.csdn.net，作者：小小谢先生，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/xiewenrui1996/article/details/90609539