算法导论练习题

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

• 一、2.1插入排序
• 2.1插入排序
• • 2.1-2
  • 2.1-3
  • 2.1-4
• 2.2分析算法
• • 2.2-1
  • 2.2-2
  • 2.2-3
  • 2.2-4
• 总结

遍历列表的第二个元素到最后一个元素，每次拿后面的元素与前面的元素做比较找到合适的插入位置采用一个for循环套一个while循环实现。
θ theta θ=（n²）

代码如下（示例）：

class Solution(object):
    def generate(self, A):
        """
        :type numRows: int
        :rtype: List[List[int]]
        """
        for j in range(1,len(A)):
            key=A[j]
            i=j-1
            while i>=0 and A[i] 
2.1-3 
代码如下（示例）：
 
class Solution(object):
    def generate(self, A,b):
        """
        :type numRows: int
        :rtype: List[List[int]]
        """
        for i in range(len(A)):
            if A[i]==b:
                return i
        return False
a=Solution()            
print(a.generate([5,2,4,6,1,3],3))
 
2.1-4 
代码如下（示例）：
 
class Solution:
    def addBinary(self, a, b):
        return '{0:b}'.format(int(a, 2) + int(b, 2))
a=Solution()            
print(a.addBinary(  "1010","1011"))
 
2.2分析算法 
2.2-1 
 
（
    
     
      
       
        θ
       
      
      
       theta
      
     
    θ=n3）
 忽略低阶项和最重要项的常系数
 
2.2-2 
选择算法：找到A中最小的元素将其与
    
     
      
       
        A
       
       
        [
       
       
        1
       
       
        ]
       
      
      
       A[1]
      
     
    A[1]互换，再找到次最小元素将其与
    
     
      
       
        A
       
       
        [
       
       
        2
       
       
        ]
       
      
      
       A[2]
      
     
    A[2]互换，对A中的前
    
     
      
       
        (
       
       
        n
       
       
        −
       
       
        1
       
       
        )
       
      
      
       (n-1)
      
     
    (n−1)个元素按照该方式继续下去
 代码如下（示例）：
 
#采用while 循环
class Solution(object):
    def generate(self, A):
        """
        :type numRows: int
        :rtype: List[List[int]]
        """
        k=0
        while k 
（
    
     
      
       
        θ
       
      
      
       theta
      
     
    θ=n2）最好和最坏情况运行时间相同
 
 
2.2-3 
 
最好情况：1
 最糟糕情况：n
 平均情况：
    
     
      
       
        
         n
        
        
         2
        
       
      
      
       {n}over{2}
      
     
    2n​
 忽略低阶项和重要项的常数项系数后平均情况和糟情况都是（
    
     
      
       
        θ
       
       
        =
       
       
        n
       
      
      
       theta=n
      
     
    θ=n）
 
2.2-4 
 
测试最糟糕情况
 
 
总结