从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:
				return 1
		else :
			p = i
			c = 1
		#print i, p, c

	return 0

这是我要记住的一课。