算法分析

第二章 算法分析

（1）大O记法

python
# 数量级（order of magnitude）常被称作大O记法（order），记作O(f(n))

# 示例：
def order(n):
    """
    T(n) = 3 + 3n2 + 2n + 1, 时间复复杂度是O(n2)
    :param n:
    :return:
    """
    a = 5
    b = 6
    c = 10
    for i in range(n):
        for j in range(n):
            x = i * i
            y = j * j
            z = i * j
    for k in range(n):
        w = a * k + 45
        v = b * b
    d = 33

（2） 异序词检测

python
"""
展示不用数量级算法的经典例子：异序词检测
题目：如果一个字符串只是重排了另一个字符串的字符，那么这个字符串就是另一个的异序词。长度相同，小写字母。
"""


def anagramSolution1(s1, s2):
    """
    方法一：清点法，时间复杂度0(n2)
    思路：清点s1，判断是否都出现在list(s2)。通过用python中的特殊值None替换s2字符实现。但str不可修改，所以需要先转换成列表。
    :param s1:
    :param s2:
    :return: 布尔值，是否为异序词
    """
    s2list = list(s2)

    pos1 = 0
    still_ok = True
    while pos1 < len(s1) and still_ok:
        pos2 = 0
        found = False
        while pos2 < len(s2list) and not found:
            if s1[pos1] == s2list[pos2]:
                found = True
            else:
                pos2 += 1
        if found:
            s2list[pos2] = None
        else:
            still_ok = False
        pos1 += 1
    return still_ok


def anagramSolution2(s1, s2):
    """
    方法二：排序法，时间复杂度O(n2)或者O(nlogn)
    思路：字符串转换成列表，再使用sort()排序
    :param s1:
    :param s2:
    :return:
    """
    s1list = list(s1)
    s2list = list(s2)

    s1list.sort()
    s2list.sort()

    pos = 0
    matches = True
    while pos < len(s1list) and matches:
        if s1list[pos] == s2list[pos]:
            pos += 1
        else:
            matches = False
    return matches


def anagramSolution3(s1, s2):
    """
    方法三：计数法，时间复杂度O(n),空间换时间
    思路：数每个字符出现的次数，26种字符对应26个计数器，每遇到1个字符，计算器+1；最后判断2个列表是否相等
    :param s1:
    :param s2:
    :return: 布尔值，是否为异序词
    """
    c1, c2 = [0] * 26, [0] * 26

    for i in range(len(s1)):
        pos = ord(s1[i]) - ord('a')
        c1[pos] += 1

    for i in range(len(s2)):
        pos = ord(s2[i]) - ord('a')
        c2[pos] += 1

    if c1 == c2:
        return True
    else:
        return False



s1 = 'earjj'
s2 = 'jearj'
print(anagramSolution3(s1, s2))

（3）性能分析

python
# -*- coding: utf-8 -*-#
# -------------------------------------------------------------------------------
# Name:         3_性能分析
# Description:  Python数据结构的性能分析
# Author:       zhaoyaowei
# Date:         2023/2/17 20:54
# -------------------------------------------------------------------------------
from timeit import Timer
import random


# 生成列表的4种方式
def test1():
    """
    第一种：列表连接
    :return:
    """
    a = []
    for i in range(1000):
        a = a + [i]


def test2():
    """
    第一种：列表追加
    :return:
    """
    a = []
    for i in range(1000):
        a.append(i)


def test3():
    """
    第二种：列表解析式
    :return:
    """
    a = [i for i in range(1000)]


def test4():
    """
    第三种：列表构造器调用range函数
    :return:
    """
    a = list(range(1000))


number = 1000
# from __main__ import test1 将test1()从__main__命名空间导入值timeit设置计时的命名空间
# 构造函数接收计时的语句、用于设置的语句和计时器函数。
t1 = Timer("test1()", "from __main__ import test1")
print(f"列表连接运行{number}次耗时：", t1.timeit(number=number), "毫秒")
t2 = Timer("test2()", "from __main__ import test2")
print(f"列表追加运行{number}次耗时：", t2.timeit(number=number), "毫秒")
t3 = Timer("test3()", "from __main__ import test3")
print(f"列表解析式运行{number}次耗时：", t3.timeit(number=number), "毫秒")
t4 = Timer("test4()", "from __main__ import test4")
print(f"列表构造器运行{number}次耗时：", t4.timeit(number=number), "毫秒")

# 比较列表和字段的包含操作
for i in range(10000, 1000001, 20000):
    t = Timer("random.randrange(%d) in x" % i, "from __main__ import random, x")
    x = list(range(i))
    lst_time = t.timeit(number=number)

    x = {j: None for j in range(i)}
    dct_time = t.timeit(number=number)

    print("%d, %10.3f, %10.3f" % (i, lst_time, dct_time))