Pyhton数据结构与算法-线性表（顺序表）

系统管理员 2022-05-14 06:50 357阅读 0赞

## 算法的五大特性 ##

1.  **输入**: 算法具有0个或多个输入
2.  **输出**: 算法至少有1个或多个输出
3.  **有穷性**: 算法在有限的步骤之后会自动结束而不会无限循环，并且每一个步骤可以在可接受的时间内完成
4.  **确定性**：算法中的每一步都有确定的含义，不会出现二义性
5.  **可行性**：算法的每一步都是可行的，也就是说每一步都能够执行有限的次数完成

import time 
    start = time.clock()
    for a in range(1001):
        for b in range(1001):
            c = 1000 - a - b 
            if a**2 + b**2 == c**2:
                print('%d^2 + %d^2 = %d^2'%(a, b, c))
    end = time.clock()
    print('花费的时间为：%.3f'%(end - start))
    # 0^2 + 500^2 = 500^2
    # 200^2 + 375^2 = 425^2
    # 375^2 + 200^2 = 425^2
    # 500^2 + 0^2 = 500^2
    # 花费的时间为：1.825

算法效率衡量：单纯依靠运行时间来比较算法的优劣并不一定准确。程序的运行离不开计算机环境（硬件和操作系统）的影响。

> **时间复杂度和‘大O记法’：**
> 
> “大O记法”：对于单调的整数函数f，如果存在一个整数函数g和实常数c>0，使得对于充分大的n总有f(n)<=c\*g(n)，就说函数g是f的一个渐近函数（忽略常数），记为f(n)=O(g(n))。也就是说，在趋向无穷的极限意义下，函数f的增长速度受到函数g的约束，亦即函数f与函数g的特征相似。
> 
> 时间复杂度：假设存在函数g，使得算法A处理规模为n的问题示例所用时间为T(n)=O(g(n))，则称O(g(n))为算法A的渐近时间复杂度，简称时间复杂度，记为T(n)

## 时间复杂度的几条基本计算规则 ##

> 1.  基本操作，即只有常数项，认为其时间复杂度为O(1)
> 2.  顺序结构，时间复杂度按**加法**进行计算
> 3.  循环结构，时间复杂度按**乘法**进行计算
> 4.  分支结构，时间复杂度**取最大值（最坏时间复杂度）**
> 5.  判断一个算法的效率时，往往只需要关注操作数量的最高次项，其它次要项和常数项可以忽略
> 6.  在没有特殊说明时，我们所分析的算法的时间复杂度都是指**最坏时间复杂度**

大O阶推导（类似于求无穷大）：

1.  将常数项改为 1
2.  只保留最高项
3.  去除此项相乘的常数

常见时间复杂度：

<table> 
 <thead> 
  <tr> 
   <th>执行次数函数举例</th> 
   <th>阶</th> 
   <th>非正式术语</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>12</td> 
   <td>O(1)</td> 
   <td>常数阶</td> 
  </tr> 
  <tr> 
   <td>2n+3</td> 
   <td>O(n)</td> 
   <td>线性阶</td> 
  </tr> 
  <tr> 
   <td>3n^2+2n+1</td> 
   <td>O(n^2)</td> 
   <td>平方阶</td> 
  </tr> 
  <tr> 
   <td>5log2n+20</td> 
   <td>O(logn)</td> 
   <td>对数阶</td> 
  </tr> 
  <tr> 
   <td>2n+3nlog2n+19</td> 
   <td>O(nlogn)</td> 
   <td>nlogn阶（线性对数阶）</td> 
  </tr> 
  <tr> 
   <td>6n^3+2n^2+3n+4</td> 
   <td>O(n^3)</td> 
   <td>立方阶</td> 
  </tr> 
  <tr> 
   <td>2^n</td> 
   <td>O(2^n)</td> 
   <td>指数阶</td> 
  </tr> 
 </tbody> 
</table>

**注意，经常将log2n（以2为底的对数）简写成logn**

对应的图像：

![70][]

所消耗的时间从小到大

**O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)**

**小于O（n^2）的时间复杂度的算法效率比较好。**

#线性阶
    for i in range(n):
        '时间复杂度为O(1)的程序'
    
    #对数阶
    count = 1
    while(count < n):
        count *= 2
        '时间复杂度为O(1)的程序'
    # 2^x = n --> x = log2 n   
    
    #平方阶
    for i in range(n):
        for i in range(n):
            '时间复杂度为O(1)的程序'
    
    for i in range(n):
        for j in range(i, n):
            '时间复杂度为O(1)的程序' # 执行了 n + (n-1) +(n-2)....1 = (n+1)n/2 还是 O(n^2)
    def function(count):
        for j in range(count, 10):
            print(j)
    f = function(2) #最终的时间复杂度为O(n^2)

**例子：**

python内置类型性能分析  
timeit 模块用来测试一小段python代码的执行速度。  
timeit.Timer(stmt = 'pass'(statement代码语句), setup= 'pass', timer = <timer function>  
timeit.Timeit.timeit(number = 1000) number表示测试的次数，返回执行代码的平均数

#list的4中写入方式
    def test1():
        li = []
        for i in range(10000):
            li += [i]
            
    def test2():
        li = []
        for i in range(10000):
            li.append(i)
        
    def test3():
        li = [i for i in range(10000)]
    
    def test4():
        li = list(range(10000))
        
    from timeit import Timer
    t1 = Timer('test1()', 'from __main__ import test1')
    print('concat',t1.timeit(number=1000), 's')
    t2 = Timer('test2()', 'from __main__ import test2')
    print('append', t2.timeit(number= 1000), 's')
    t3 = Timer('test3()', 'from __main__ import test3')
    print('comprehension列表解析 : ', t3.timeit(1000), 's')
    t4 = Timer('test4()', 'from __main__ import test4')
    print('list range', t4.timeit(1000), 's')
    # concat 1.8211973571964015 s
    # append 1.1640232883314492 s
    # comprehension列表解析 :  0.5225764789822889 s
    # list range 0.3116341488847234 s

### 1.顺序表： ###

顺序表，将元素顺序地存放在一块连续的存储区里，元素间的顺序关系由它们的存储顺序自然表示。

# 顺序表，将元素顺序地存放在一块连续的存储区里，元素间的顺序关系由它们的存储顺序自然表示。
    #顺序表的实现：
    class SeqList():
        def __init__(self, max=8):
            self.max = max 
            self.num = 0    #计算列表内的数据的个数，在append函数
            self.date = [None] * self.max
    #     def add(self):
    #         if self.num > int(self.max *2 /3):
    #             self.max *= 2
            
        def is_empty(self):
            return self.num == 0
        def is_full(self):
            return self.num == self.max 
        
        def __getitem__(self, key):
            '''获取某个位置的值'''
            print(key)
            if not isinstance(key, int): #验证key值是否是整数
                raise TypeError
            if 0 <=key < self.num:
                return self.date[key]
            else:
                raise IndexError
         
        def __setitem__(self, key, value):
            '''依据键值， 设置某个位置的值'''
            if not isinstance(key, int):
                raise TypeError
            if 0 <= key < self.num:
                self.date[key] = value 
            else:
                raise IndexError
        def __len__(self):
            return self.num 
        def count(self):
            return self.num
        def clear(self):
            self.__init__()
        def show(self):
            for i in range(self.num):
                print(self.date[i], end=' ')
            print()
    
         
        def append(self, value):
            '''定义增加数据的方法'''
            if not self.is_full():
                self.date[self.num] = value 
                self.num += 1
            else:
                print('the sequent lists are full')
                return
        
        def insert(self, key, value):
            '''定义插入对应键值得数据'''
            if not isinstance(key, int):
                raise TypeError
            if key < 0:
                raise IndexError
            if key >= self.num:
                self.append(value)
                
            else:   #如果正常插入数据，插入的key， 将从key开始全部数据后移
                for i in range(self.num, key, -1):
                    self.date[i] = self.date[i-1]
                self.date[key] = value 
                self.num += 1
                
        def pop(self, key = -1):
            '''删除对应位置的值'''
            if not isinstance(key, int):
                raise TypeError 
            if self.num - 1 < 0:
                raise IndexError('数据为空')
            elif key == -1:
                self.num -= 1
            elif key >= self.num:
                print('input key error')
            else:
                for i in range(key, self.num):
                    self.date[i] = self.date[i+1]   #将数字前移动
                self.num -= 1
        def index(self, value, start=0):
            '''获取对应键的值'''
            for i in range(start, self.num):
                if self.date[i] == value:
                    return i
                else:
                    raise ValueError('%d is not in list'%value)
        
        def reverse(self):
            '''将顺序表进行反转'''
            i, j = 0, self.num -1
            while i < j:
                self.date[i], self.date[j] = self.date[j], self.date[i]
                i, j = i+1, j-1
            
    s = SeqList()
    print(s.date) # 返回多个None [None, None, None, None, None, None, None, None]
    print(s.is_empty())     # True
    # print(s.__getitem__(1))
    s.append(1)
    s.append(2)
    print(s.count())    #2
    s.show()    # 1 2 
    # s.clear()
    # print(s.count())
    s.insert(1,20)
    # print(s.count())
    s.show()    # 1 20 2
    s.pop(1)
    s.show()    # 1 2 
    s.reverse()
    s.show()    #  2 1 
    print(s.index(2))   # 0

[顺序表参考-小黄人python][-_python]

[70]: /images/20220514/eec9bbda53924cee8b1c0b50ea4b057e.png
[-_python]: https://www.cnblogs.com/xautxuqiang/p/6098137.html