程序员最近都爱上了这个网站  程序员们快来瞅瞅吧!  it98k网:it98k.com

本站消息

站长简介/公众号

  出租广告位,需要合作请联系站长

+关注
已关注

分类  

暂无分类

标签  

暂无标签

日期归档  

2021-12(24)

2022-01(11)

数据结构之算法

发布于2019-08-20 10:17     阅读(1014)     评论(0)     点赞(0)     收藏(3)


1.算法性能评估

1.度量算法的运行时间

使用计算机的时钟来获取一个实际的运行时间
  • 1

2.统计指令

统计对不同的问题规模索要执行的指令的数目
1.不管问题规模多大,都执行相同的次数的指令
2.根据问题的规模,执行不同次数的指令

# 循环中
problemSize = 1000
print("%12s%15s" % ("problem size", "Iterations"))
for count in range(5):
    number = 0
    # The start of the algorithm
    work = 1
    for j in range(problemSize):
        for k in range(problemSize):
            number += 1
            work += 1
            work -= 1
    # the end of the algorithm
    print("%12d%15d" % (problemSize, number))
    problemSize *= 2
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
运行结果:
	problem size     Iterations
        1000        1000000
        2000        4000000
        4000       16000000
        8000       64000000
       16000      256000000
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
# 递归
# counter类见上一章
from counter import Counter

def fib(n, counter):
	"""计算调用斐波那契函数的次数"""
	counter.increment()
	if n < 3:
		return 1
	else:
		return fib(n-1, counter) + fib(n-2, counter)

problemSize = 2
print("%12s%15s % ('Problem Size', 'Calls'))
for count in range(5):
	counter = Counter()
	fib(problemSize, counter)
	print("%12d%15s" % (problemSize, counter))
	problemSize *=2
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
Problem Size	  Calls
       2			1
       4			5
       8			41
      16			1973
      32        	4356617
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

3.度量算法使用的内存

2.复杂度分析

2.1复杂度的阶

O表示,一个线性时间算法的阶是O(n)

2.2最坏时间复杂度

  • 算法完成工作最少需要多少基本操作,最优时间复杂度
  • 算法完成工作最多需要多少基本操作,最坏时间复杂度
  • 算法完成工作平均需要多少基本操作,平均时间复杂度

2.3时间复杂度的基本计算规则

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

3.搜索算法

3.1 搜索最小值

复杂度是O(n)

lst = [1, 4, 5, 3, 2, 0, 6, 7]
def indexOfMin(lyst):
	"""Returns the index of the minimum item"""
	minIndex = 0
	currentIndex = 1
	while currentIndex < len(lyst):
		if lyst[currentIndex] < lyst[minIndex]:
			minIndex = currentIndex
		currentIndex += 1
	return minIndex

print(indexOfMin(lst))		# 返回列表最小值的索引
print(lst[indexOfMin(lst)])	# 打印最小值
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
5
0
  • 1
  • 2

3.2顺序搜索一个无序列表

复杂度是O(n)

lst = [1, 4, 5, 3, 2, 0, 6, 7]

def sequentialSearch(target, lyst):
    """Returns the postion of the target item if found,or -1 otherwise"""
    position = 0
    while position < len(lyst):
        if target == lyst[position]:
            return position
        position += 1
    return -1

print(sequentialSearch(5, lst))		# 打印目标值在列表中的索引位置
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
2
  • 1

3.3有序列表的二分法搜索

复杂度O(log₂N)

lst = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

def binarySearch(target, sortedLyst):
    left = 0
    right = len(sortedLyst) -1 
    while left <= right:
        midpoint = (left + right) // 2
        if target == sortedLyst[midpoint]:
            return midpoint
        elif target < sortedLyst[midpoint]:
            right = midpoint - 1
        else:
            left = midpoint + 1
    return -1

print(binarySearch(5, lst))		# 打印目标值列表索引
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
4
  • 1

3.4比较数据项

class SavingsAccount(object):
    def __init__(self, name, PIN, balance = 0.0):
        self._name = name
        self._PIN = PIN
        self._balance = balance

    def __lt__(self, other):
        return self._name < other._name

    def __eq__(self, other):
        return self._name == other._name
        
s1 = SavingsAccount("Knight", "1000", "0")
s2 = SavingsAccount("Queen", "1001", "30")
s3 = SavingsAccount("Knight", "1000", "0")
print(s2 < s1)
print(s3 == s1)
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
False
True
  • 1
  • 2

4.基本排序算法

基本的排序算法都用的函数

lst = [1, 3, 2, 4]

def swap(lyst, i, j):
    """Exchange the items at position i and j"""
    # lyst[i], lyst[j] = lyst[j], lyst[i]
    temp = lyst[i]
    lyst[i] = lyst[j]
    lyst[j] = temp

swap(lst, 1, 2)
print(lst)
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
[1, 2, 3, 4]
  • 1

4.1选择排序

复杂度O(n²)

# swap方法见上面
lst = [5, 3, 2, 1, 4]

def selectionSort(lyst):
    i = 0
    while i < len(lyst) - 1:
        minIndex = i
        j = i + 1
        while j < len(lyst):
            if lyst[j] < lyst[minIndex]:
                minIndex = j
            j += 1
        if minIndex != i:
            swap(lyst, minIndex, i)
        i += 1

selectionSort(lst)
print(lst)
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
[1, 2, 3, 4, 5]
  • 1

4.2冒泡排序

复杂度O(n²)

lst = [5, 3, 2, 1, 4]

def bubbleSort(lyst):
    n = len(lyst)
    while n > 1:
        i = 1
        while i < n:
            if lyst[i] < lyst[i-1]:
                swap(lyst, i, i-1)
            i += 1
        n -= 1

bubbleSort(lst)
print(lst)
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
[1, 2, 3, 4, 5]
  • 1

4.3插入排序

复杂度O(n²)

lst = [5, 3, 2, 1, 4]
def insertionSort(lyst):
    i = 1
    while i < len(lyst):
        itemToInsert = lyst[i]
        j = i - 1
        while j >= 0:
            if itemToInsert < lyst[j]:
                lyst[j + 1] = lyst[j]
                j -= 1
            else:
                break
        lyst[j + 1] = itemToInsert
        i += 1
insertionSort(lst)
print(lst)
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
[1, 2, 3, 4, 5]
  • 1

5.更快排序

5.1快速排序

复杂度O(n²)

import random

def swap(lyst, i, j):
    """Exchange the items at position i and j"""
    # lyst[i], lyst[j] = lyst[j], lyst[i]
    temp = lyst[i]
    lyst[i] = lyst[j]
    lyst[j] = temp

def quicksort(lyst):
    quicksortHelper(lyst, 0, len(lyst) - 1)

def quicksortHelper(lyst, left, right):
    if left < right:
        pivotLocation = partition(lyst, left, right)
        quicksortHelper(lyst, left, pivotLocation - 1)
        quicksortHelper(lyst, pivotLocation + 1, right)

def partition(lyst, left, right):
    # Find the pivot and exchange it with the last item
    middle = (left + right) // 2
    pivot = lyst[middle]
    lyst[middle] = lyst[right]
    lyst[right] = pivot
    # Set boundarypoint to first position
    boundary = left
    # Move items less than pivot to the left
    for index in range(left, right):
        if lyst[index] < pivot:
            swap(lyst, index, boundary)
            boundary += 1
    # Exchange definition of the swap function goes here
    swap(lyst, right, boundary)
    return boundary

def main(size=20, sort=quicksort):
    lyst = []
    for count in range(size):
        lyst.append(random.randint(1, size + 1))
    sort(lyst)
    print(lyst)

if __name__ == "__main__":
    main()
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
随机列表快速排序
  • 1

5.2合并排序

复杂度O(nlogn)

class Array(object):
    def __init__(self, capacity, fileValue=None):
        """
        :param capacity: 数组容量的大小
        :param fileValue: 数组每个位置的值
        """
        self._items = list()
        for count in range(capacity):
            self._items.append(fileValue)

    def __len__(self):
        """
        数组容量的大小
        """
        return len(self._items)

    def __str__(self):
        """
        数组的字符串表示形式
        """
        return str(self._items)

    def __iter__(self):
        """
        支持遍历for循环
        """
        return iter(self._items)

    def __getitem__(self, index):
        """
        用于索引访问的下标运算符
        """
        return self._items[index]

    def __setitem__(self, index, newItem):
        """
        在索引处替换的下标运算符
        """
        self._items[index] = newItem

def mergeSort(lyst):
    """
    :param lyst: # 列表排序
    """
    copyBuffer = Array(len(lyst))   # 合并期间需要的临时空间
    mergeSortHelper(lyst, copyBuffer, 0, len(lyst) - 1)

def mergeSortHelper(lyst, copyBuffer, low, high):
    """
    :param lyst:    # 列表排序
    :param copyBuffer: # 合并期间需要的临时空间
    :param low, high:  # 子表的边界
    :param middle:  # 子表的中间
    """
    if low < high:
        middle = (low + high) // 2
        mergeSortHelper(lyst, copyBuffer, low, middle)
        mergeSortHelper(lyst, copyBuffer, middle + 1, high)
        merge(lyst, copyBuffer, low, middle, high)

def merge(lyst, copyBuffer, low, middle, high):
    """
    :param lyst: # 正在排序的列表
    :param copyBuffer: # 合并过程中需要的临时空间
    :param low: # 第一个排序子列表的开头
    :param middle: # 第一个排序子列表的结尾
    :param middle + 1: # 第二个排序子列表的开头
    :param high: # 第二个排序子列表的结尾
    """
    i1 = low
    i2 = middle + 1
    for i in range(low, high + 1):
        if i1 > middle:
            copyBuffer[i] = lyst[i2]    # 第一个子列表用尽了
            i2 += 1
        elif i2 > high:
            copyBuffer[i] = lyst[i1]    # 第二个子列表用尽了
            i1 += 1
        elif lyst[i1] < lyst[i2]:
            copyBuffer[i] = lyst[i1]    # 第一个子列表中的项目
            i1 += 1
        else:
            copyBuffer[i] = lyst[i2]    # 第二个子列表中的项目
            i2 += 1

    for i in range(low, high + 1):      # 将已排序的项目复制回列表中的正确位置
        lyst[i] = copyBuffer[i]

lst = [4, 1, 7, 6, 5, 3, 8, 2]

mergeSort(lst)
print(lst)
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
[1, 2, 3, 4, 5, 6, 7, 8]
  • 1

6.Fibonacci算法

6.1Fibonacci指数算法

复杂度O(K^n) ==> k = 1.63

def  fib(n):
	# 斐波那契函数的递归
	if n < 3:
		return 1
	else:
		return fib(n -1) + fib(n -2)
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

6.2Fibonacci线性算法

复杂度O(n)

class Counter(object):
    """Models a counter。"""

    # Class variable
    instance = 0

    # Constructor
    def __init__(self):
        """Sets up the counter"""
        Counter.instance += 1
        self.reset()        # 初始化对象,

    # Mutator methods   # 修改器
    def reset(self):
        """Sets the Counter to 0"""
        self._value = 0

    def increment(self, amount=1):
        """Adds amount to the counter"""
        self._value += amount

    def decrement(self, amount=1):
        """Subtracts amount from the counter"""
        self._value -= amount

    # Accessor methods  # 访问器
    def getValue(self):
        """Returns The counter`s values"""
        return self._value

    def __str__(self):
        """Returns the string representation of the counter"""
        return  str(self._value)

    def __eq__(self, other):
        """Returns True if self equals other or False otherwise"""
        if self is other:
            return True
        if type(self) != type(other):
            return False
        return self._value == other._value

problemSize = 2

def fib(n, counter):
    # 计算斐波那契函数的迭代次数
    sum = 1
    first = 1
    second = 1
    count = 3
    while count <= n:
        counter.increment()
        sum = first + second
        first = second
        second = sum
        count += 1

    return sum

print("%12s%15s" % ('Problem Size', 'Iterations'))
for count in range(5):
    counter = Counter()
    fib(problemSize, counter)
    print("%12d%15s" % (problemSize, counter))
    problemSize *= 2
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
Problem Size          Iterations
       2              		0
       4              		2
       8              		6
      16             		14
      32             		30
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6


所属网站分类: 技术文章 > 博客

作者:站起来

链接:https://www.pythonheidong.com/blog/article/48954/b969e156311c676305be/

来源:python黑洞网

任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任

0 0
收藏该文
已收藏

评论内容:(最多支持255个字符)