-
从6.7到0.01
编程果然不能偷懒！我这一偷懒，CPU就不知道要受多少累、冒多少热气了。一开始，我采用了很无脑的穷举方法，复杂度是O(n**2)，结果肯定正确的，但是长度一万的数组就可以耗去6.7秒的CPU时间。 raymond@raymond-laptop:~/_Work/Dev/python$ python le.py time: 0:00:06.708924 return: 1 0 0 0 之后，在高手提示下将复杂度降低到n (log n + 1) ，结果不错了。 raymond@raymond-laptop:~/_Work/Dev/python$ python le.py time: 0:00:00.010430 return: 1 0 0 0 对应改进后的代码： def leader3(array): t = len(array) //2 array.sort() p = -1 c = 1 for i in array: if p == i : c+=1 if c > t:…
-
偷闲，写了个初级二叉树排序
二叉树是计算机算法中普遍采用的数据结构。在所有排序算法中具有高效率的二叉树排序就是基于此结构。我抽空用新学的Python写了一个试试： class node: left = None right = None value = 0 def __init__(self, v): self.value = v def walk(self): r = [] if self.left: r.extend(self.left.walk()) r.append(self.value) if self.right: r.extend(self.right.walk()) return r def insert(self, n): if self.value < n: if self.right: self.right.insert(n) else: self.right = node(n) else: if self.left: self.left.insert(n) else: self.left = node(n) if…