＜学习笔记＞数据+算法初识+python数据结构结构性能分析(2020.7.22）

1.什么是计算机科学？

• 计算机科学实际上是对问题以及解决问题过程中产生的解决方案得研究。例如给定一个问题，计算机科学家目标是开发出一个算法来处理该问题，最终得到该问题的解决方法，最共得到该问题得解或是最优解。

2.评判程序优劣得方法

• 消耗计算机得资源和执行效率(无法直观）
• 算法得执行耗时(不推荐，受到机器和执行环境的影响
• 时间复杂度(推荐）

3.时间复杂度

• 评价标准：量化算法执行操作/执行步骤得数量
• 最重要的项：时间复杂度表达式中最有意义的项
• 使用大O记法，来表示时间复杂度——O(最重要的项)
• 常见的时间复杂度如下图
  

4.数据结构

• 概念：对于数据(基本类型(int,float,char))得组织形式就被称为数据结构，数据结构解决的就是一组数据如何保存，保存的形式是怎样的。
• 总结：使用不同形式组织数据，在基于查询时得时间复杂度是不一样的。因此算法是为了解决实际问题而设计得，数据结构是算法处理问题得载体。

5.数据结构性能分析python

了解python列表和字典操作的大O性能，通过时间实验来说明每个数据结构得花销和使用这些数据结构得好处

• timeit模块：该模块可以测试一段代码得执行速度
• Timer类：是timeit中专门用来测试代码sh时长

函数：timeit.Timer（stmt=‘pass’, setup=‘pass’)

• stmt：指将要运行得代码块
• timeit函数：timeit.Timer.timeit(number=100000)该函数表示代码块执行number次平均消耗时常。

例：实例化一个空列表，将0-n范围内数据添加到列表中(4种)

# python自带数据结构得运行效率测试
# 实例化一个空列表，然后将0-n范围的数据增加到列表种

def test0():
    alist = []
    for i in range(1000):
        alist += [i]
    return alist

def test1():
    alist = []
    for i in range(1000):
        alist.append(i)
    return alist

def test2():
    alist = [i for i in range(1000)] # 列表生成式
    return alist
def test3():
    alist = list(range(1000))
    return alist

if __name__ == '__main__':

    from timeit import Timer

    timer = Timer()

    t0 = Timer("test0()", "from __main__ import test0")
    print("concat ",t0.timeit(number=1000))

    t1 = Timer("test1()", "from __main__ import test1")
    print("append ",t1.timeit(number=1000))

    t2 = Timer("test2()", "from __main__ import test2")
    print("comprehension ",t2.timeit(number=1000))

    t3 = Timer("test3()", "from __main__ import test3")
    print("list range ",t3.timeit(number=1000))

测试结果如下：

本文地址：https://blog.csdn.net/qq_45363979/article/details/107536626