Tag: 算法

  • 从6.7到0.01

    编程果然不能偷懒!我这一偷懒,CPU就不知道要受多少累、冒多少热气了。一开始,我采用了很无脑的穷举方法,复杂度是O(n**2),结果肯定正确的,但是长度一万的数组就可以耗去6.7秒的CPU时间。 [email protected]:~/_Work/Dev/python$ python le.py time:  0:00:06.708924 return:  1 0 0 0 之后,在高手提示下将复杂度降低到n (log n + 1) ,结果不错了。 [email protected]:~/_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 […]