1:algorithm is a generic, step-by-step list of instructions for solving a problem.
算法分析是一种独立于实现的度量算法。
2: Big-O Notation
Big-O标记使算法可以根据问题的大小按其主导过程进行分类
Computer scientists prefer to take this analysis technique one step further. It turns out that the exact number of operations is not as important as determining the most dominant part of the T(n) function. In other words, as the problem gets larger, some portion of the T(n) function tends to overpower the rest. This dominant term is what, in the end, is used for comparison. The order of magnitude function describes the part of T(n) that increases the fastest as the value of n increases. Order of magnitude is often called Big-O notation (for “order”) and written as O(f(n)). It provides a useful approximation to the actual number of steps in the computation. The function f(n) provides a simple representation of the dominant part of the original T(n).
f(n) Name
1 Constant (不变)
logn Logarithmic（对数）
n Linear（线性）
nlogn Log Linear（对数线性）
n2（平方） Quadratic（二次方）
n3 （立方） Cubic（立方）
2n（n次方） Exponential（指数）
随着N 越大，运行的时间越长，对资源的消耗越多
3: List - Python
Big-O Efficiency of Python List Operators
Operation Big-O Efficiency
index [] O(1)
index assignment O(1)
append O(1)
pop() O(1)
pop(i) O(n)
insert(i,item) O(n)
del operator O(n)
iteration O(n)
contains (in) O(n)
get slice [x:y] O(k)
del slice O(n)
set slice O(n+k)
reverse O(n)
concatenate O(k)
sort O(n log n)
multiply O(nk)
4：Dict Python
Big-O Efficiency of Python Dictionary Operations
operation Big-O Efficiency
copy O(n)
get item O(1)
set item O(1)
delete item O(1)
contains (in) O(1)
iteration O(n)
5： 线性数据结构
linear data structures： 堆栈，队列，双端队列和列表
数据项的添加顺序取决于其添加或删除的方式。添加项目后，它相对于之前和之后的其他元素保持在该位置。
线性结构可以认为具有两个末端。有时将这些末端称为“左”和“右”，在某些情况下称为“前”和“后”。您也可以将它们称为“顶部”和“底部”。结尾处的名称并不重要。一种线性结构与另一种线性结构的区别是添加和删除项目的方式，尤其是这些添加和删除发生的位置。例如，一种结构可能允许仅在一端添加新项目。一些结构可能允许从任一端删除项目。
6：堆栈（Stack）
堆栈（有时被称为“压入堆栈”）是项目的有序集合，其中的新项目的添加和移除现有的项目中总是发生在同一端。此末端通常称为“顶部”。与顶部相对的一端称为“底座”。
堆栈的操作上LIFO （先进后出，后进先出）
7：堆栈数据类型 （Stack Abstract Data Type）
Stack() creates a new stack that is empty. It needs no parameters and returns an empty stack.
push(item) adds a new item to the top of the stack. It needs the item and returns nothing.
pop() removes the top item from the stack. It needs no parameters and returns the item. The stack is modified.
peek() returns the top item from the stack but does not remove it. It needs no parameters. The stack is not modified.
isEmpty() tests to see whether the stack is empty. It needs no parameters and returns a boolean value.
size() returns the number of items on the stack. It needs no parameters and returns an integer.
堆栈操作 堆栈内容 返回值
s.isEmpty() [] True
s.push(4) [4]
s.push('dog') [4,'dog']
s.peek() [4,'dog'] 'dog'
s.push(True) [4,'dog',True]
s.size() [4,'dog',True] 3
s.isEmpty() [4,'dog',True] False
s.push(8.4) [4,'dog',True,8.4]
s.pop() [4,'dog',True] 8.4
s.pop() [4,'dog'] True
s.size() [4,'dog'] 2
Python 实现 堆栈
class stack:
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def Push(self):
return self.items.append(item)
def pop(self):
return self.items.pop()
def peek(self):
return self.items[len(self.items)-1]
def size(self):
return len(self.items)
8： 队列（Queue）
队列是项目的有序集合，其中新项目的添加发生在一端，称为“后部”，而现有项目的删除发生在另一端，通常称为“前部”。当一个元素进入队列时，它从后面开始，朝着前面的方向前进，一直等到那是要删除的下一个元素。
队列中最近添加的项目必须在集合的末尾等待。收藏时间最长的物品在最前面。这种排序原理有时也被称为FIFO， 先入先出。也称为“先到先得”。
Queue()创建一个空的新队列。它不需要任何参数，并返回一个空队列。
enqueue(item)将新项目添加到队列的后面。它需要该项目，但不返回任何内容。
dequeue()从队列中删除最前面的项目。它不需要任何参数并返回该项目。队列已修改。
isEmpty()测试以查看队列是否为空。它不需要任何参数，并返回一个布尔值。
size()返回队列中的项目数。它不需要参数，并返回整数。
操作
队列操作 队列内容 返回值
q.isEmpty() [] True
q.enqueue(4) [4]
q.enqueue('dog') ['dog',4]
q.enqueue(True) [True,'dog',4]
q.size() [True,'dog',4] 3
q.isEmpty() [True,'dog',4] False
q.enqueue(8.4) [8.4,True,'dog',4]
q.dequeue() [8.4,True,'dog'] 4
q.dequeue() [8.4,True] 'dog'
q.size() [8.4,True] 2
Python 实现queue
class Queue:
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def enqueue(self, item):
self.items.insert(0,item)
def dequeue(self):
return self.items.pop()
def size(self):
return len(self.items)
9： 双端队列（Deque）
双端队列，类似于队列项目的有序集合。它有两个前端，一个前端和一个后端，并且项目保持在集合中。使双端队列不同的是添加和删除项的无限制性质。可以在前面或后面添加新项目。同样，可以从任一端删除现有项目。从某种意义上说，这种混合线性结构在单个数据结构中提供了堆栈和队列的所有功能。
双端队列操作 双端队列内容 返回值
d.isEmpty() [] True
d.addRear(4) [4]
d.addRear('dog') ['dog',4,]
d.addFront('cat') ['dog',4,'cat']
d.addFront(True) ['dog',4,'cat',True]
d.size() ['dog',4,'cat',True] 4
d.isEmpty() ['dog',4,'cat',True] False
d.addRear(8.4) [8.4,'dog',4,'cat',True]
d.removeRear() ['dog',4,'cat',True] 8.4
d.removeFront() ['dog',4,'cat'] True
Python 实现 双端队列
class Deque:
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def addFront(self, item):
self.items.append(item)
def addRear(self, item):
self.items.insert(0,item)
def removeFront(self):
return self.items.pop()
def removeRear(self):
return self.items.pop(0)
def size(self):
return len(self.items)
Example: 双端队列做回文检查
from pythonds.basic import Deque
def palchecker(aString):
chardeque = Deque()
for ch in aString:
chardeque.addRear(ch)
stillEqual = True
while chardeque.size() > 1 and stillEqual:
first = chardeque.removeFront()
last = chardeque.removeRear()
if first != last:
stillEqual = False
return stillEqual
print(palchecker("ABCDCBA"))
9 无序列表 - 链表(Linked Lists)
def __init__(self,initdata):
self.data = initdata
self.next = None
def getData(self):
return self.data
def getNext(self):
return self.next
def setData(self,newdata):
self.data = newdata
def setNext(self,newnext):
self.next = newnext
>>> temp = Node(93)
>>> temp.getData()
93
Summary:
线性数据结构以有序的方式维护其数据。
堆栈是保持LIFO（后进先出）顺序的简单数据结构。
对堆栈的基本操作是push，pop和 isEmpty。
队列是保持FIFO（先进先出）顺序的简单数据结构。
对队列的基本操作enqueue，dequeue以及isEmpty。
前缀，中缀和后缀都是编写表达式的所有方法。
堆栈对于设计评估和转换表达式的算法非常有用。
堆叠可以提供反转特性。
队列可以帮助构建时序仿真。
模拟使用随机数生成器来创建现实生活中的情况，并允许我们回答“假设”类型的问题。
双端队列是允许混合行为（例如堆栈和队列）的数据结构。
对于双端队列的基本操作addFront，addRear， removeFront，removeRear，和isEmpty。
列表是项目的集合，其中每个项目都具有相对位置。
链表实现无需任何物理存储需求即可保持逻辑顺序。
修改链接列表的开头是一种特殊情况
网友评论