No older revisions available
No older revisions available
Using Swap ver.1 ¶
{{|
Time Complexity: 2k* (k!)<sup>2</sup>/ 2k! Sigma<sub>i=1 to k </sub> ( i+1 ) (<sub> k </sub> C <sub> i </sub>) <sup> 2 <sup >
approximation: O( n<sup>2</sup> )
by metric
n time n*n nlogn
1 3 1 0.0
2 8 4 1.38629436112
3 15 9 3.295836866
.....
97 9603 9409 443.746964915
98 9800 9604 449.32681291
99 9999 9801 454.916865163
|}}
Time Complexity: 2k* (k!)<sup>2</sup>/ 2k! Sigma<sub>i=1 to k </sub> ( i+1 ) (<sub> k </sub> C <sub> i </sub>) <sup> 2 <sup >
approximation: O( n<sup>2</sup> )
by metric
n time n*n nlogn
1 3 1 0.0
2 8 4 1.38629436112
3 15 9 3.295836866
.....
97 9603 9409 443.746964915
98 9800 9604 449.32681291
99 9999 9801 454.916865163
|}}
~php
#!/usr/bin/python
def getMedian(aList):
if len(aList) < 3:
return aList[0]
n = len(aList)-1
k = n/2
maxIndex = aList.index(max(aList[0:k]))
minIndex = aList.index(min(aList[k+1:n+1]))
if aList[maxIndex] <= aList[k] <= aList[minIndex]:
return aList[k]
elif aList[maxIndex] <= aList[minIndex]:
if aList[maxIndex] > aList[k]:
swapList(aList, k, maxIndex)
elif aList[minIndex] < aList[k]:
swapList(aList, k, minIndex)
else:# aList[maxIndex] > aList[minIndex]:
swapList(aList, maxIndex, minIndex)
return getMedian(aList)
def swapList(aList, one, another):
aList[one], aList[another] = aList[another], aList[one]
def factorial(n):
if n == 0:
return 1
result = 1
for i in range(n):
result *= i+1
return result
def metric(k):
sum = 0
for i in range(0,k+1):
sum += (i+1)*(factorial(k)/factorial(i)/factorial(k-i))**2
return 2*k*(factorial(k)**2)*sum/factorial(2*k)
if __name__ == '__main__':
import sys, math
if len(sys.argv) > 2 :
if sys.argv[2] == "metric":
for i in range(1, int(sys.argv[1])):
print i, metric(i), i**2, i*math.log(i)
elif sys.argv[2] == "median":
test= range(int(sys.argv[1]))
test.reverse()
print getMedian(test)
elif sys.argv[2] == "sort":
test= range(int(sys.argv[1]))
test.reverse()
test.sort()
print test[len(test)/2]
Using Swap ver.2 ¶
almost same. Sort is always faster than mine.
~php
#!/usr/bin/python
def getMedian(aList):
if len(aList) < 3:
return aList[start]
n = len(aList)-1
k = n/2
for i in range(k):
maxIndex = aList.index(max(aList[0:k-i]))
minIndex = aList.index(min(aList[k+1+i:n+1]))
swapList(aList, k-1-i, maxIndex)
swapList(aList, k+1+i, minIndex)
if aList[maxIndex] <= aList[k] <= aList[minIndex]:
return aList[k]
elif aList[maxIndex] <= aList[minIndex]:
if aList[maxIndex] > aList[k]:
swapList(aList, k, maxIndex)
elif aList[minIndex] < aList[k]:
swapList(aList, k, minIndex)
else:# aList[maxIndex] > aList[minIndex]:
swapList(aList, maxIndex, minIndex)
def swapList(aList, one, another):
aList[one], aList[another] = aList[another], aList[one]
def factorial(n):
if n == 0:
return 1
result = 1
for i in range(n):
result *= i+1
return result
def metric(k):
sum = 0
for i in range(0,k+1):
sum += (i+1)*(factorial(k)/factorial(i)/factorial(k-i))**2
return 2*k*(factorial(k)**2)*sum/factorial(2*k)
if __name__ == '__main__':
import sys, math
if len(sys.argv) > 2 :
if sys.argv[2] == "metric":
print "n\ttime\tn*n\tnlogn"
for i in range(1, int(sys.argv[1])):
print i,'\t', metric(i), '\t',i**2, '\t', i*math.log(i)
elif sys.argv[2] == "median":
test= range(int(sys.argv[1]))
test.reverse()
print getMedian(test)
elif sys.argv[2] == "sort":
test= range(int(sys.argv[1]))
test.reverse()
test.sort()
print test[len(test)/2]
