发布于2019-08-20 10:17 阅读(1184) 评论(0) 点赞(0) 收藏(3)
使用计算机的时钟来获取一个实际的运行时间
统计对不同的问题规模索要执行的指令的数目
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
运行结果:
problem size Iterations
1000 1000000
2000 4000000
4000 16000000
8000 64000000
16000 256000000
# 递归
# 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
Problem Size Calls
2 1
4 5
8 41
16 1973
32 4356617
O表示,一个线性时间算法的阶是O(n)
1.基本操作,即只有常数项,认为其时间复杂度为O(1)
2.顺序结构,时间复杂度按加法进行计算
3.循环结构,时间复杂度按乘法进行计算
4.分支结构,时间复杂度取最大值
5.判断算法效率,关注操作数量的最高次项,其他次要项和常数项可以忽略
6.没有特殊说明,分析的算法的时间复杂度都是指最坏时间复杂度
复杂度是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)]) # 打印最小值
5
0
复杂度是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)) # 打印目标值在列表中的索引位置
2
复杂度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)) # 打印目标值列表索引
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)
False
True
基本的排序算法都用的函数
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]
复杂度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]
复杂度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]
复杂度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]
复杂度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()
随机列表快速排序
复杂度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]
复杂度O(K^n) ==> k = 1.63
def fib(n):
# 斐波那契函数的递归
if n < 3:
return 1
else:
return fib(n -1) + fib(n -2)
复杂度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
Problem Size Iterations
2 0
4 2
8 6
16 14
32 30
作者:站起来
链接:https://www.pythonheidong.com/blog/article/48954/b969e156311c676305be/
来源:python黑洞网
任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任
昵称:
评论内容:(最多支持255个字符)
---无人问津也好,技不如人也罢,你都要试着安静下来,去做自己该做的事,而不是让内心的烦躁、焦虑,坏掉你本来就不多的热情和定力
Copyright © 2018-2021 python黑洞网 All Rights Reserved 版权所有,并保留所有权利。 京ICP备18063182号-1
投诉与举报,广告合作请联系vgs_info@163.com或QQ3083709327
免责声明:网站文章均由用户上传,仅供读者学习交流使用,禁止用做商业用途。若文章涉及色情,反动,侵权等违法信息,请向我们举报,一经核实我们会立即删除!