Toggle search
Toggle menu
5.7K
415
1
62.4K
ZeroWiki
Toggle personal menu
Not logged in
Your IP address will be publicly visible if you make any edits.

중위수구하기/나휘동: Difference between revisions

From ZeroWiki
More actions
imported>Unknown
No edit summary
 
(Table transclusion repair v1)
 
(One intermediate revision by the same user not shown)
Line 1: Line 1:
= Using Swap ver.1 =
= 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 >
Time Complexity: 2k* (k!)&lt;sup&gt;2&lt;/sup&gt;/ 2k! Sigma&lt;sub&gt;i=1 to k &lt;/sub&gt; ( i+1 ) (&lt;sub&gt; k &lt;/sub&gt; C &lt;sub&gt; i &lt;/sub&gt;) &lt;sup&gt; 2 &lt;sup &gt;
approximation: O( n<sup>2</sup> )
approximation: O( n&lt;sup&gt;2&lt;/sup&gt; )
by metric
by metric
n      time    n*n    nlogn
n      time    n*n    nlogn
Line 12: Line 11:
98      9800    9604    449.32681291
98      9800    9604    449.32681291
99      9999    9801    454.916865163
99      9999    9801    454.916865163
|}}
  #!/usr/bin/python
  #!/usr/bin/python
  def getMedian(aList):
  def getMedian(aList):
   if len(aList) &lt; 3:
   if len(aList) &lt; 3:
     return aList[0]
     return aList&#91;0&#93;
   n = len(aList)-1
   n = len(aList)-1
   k = n/2
   k = n/2
   maxIndex = aList.index(max(aList[0:k]))
   maxIndex = aList.index(max(aList&#91;0:k&#93;))
   minIndex = aList.index(min(aList[k+1:n+1]))
   minIndex = aList.index(min(aList&#91;k+1:n+1&#93;))
   if aList[maxIndex] &lt;= aList[k] &lt;= aList[minIndex]:
   if aList&#91;maxIndex&#93; &lt;= aList&#91;k&#93; &lt;= aList&#91;minIndex&#93;:
     return aList[k]
     return aList&#91;k&#93;
   elif aList[maxIndex] &lt;= aList[minIndex]:
   elif aList&#91;maxIndex&#93; &lt;= aList&#91;minIndex&#93;:
     if aList[maxIndex] &gt; aList[k]:
     if aList&#91;maxIndex&#93; &gt; aList&#91;k&#93;:
       swapList(aList, k, maxIndex)
       swapList(aList, k, maxIndex)
     elif aList[minIndex] &lt; aList[k]:
     elif aList&#91;minIndex&#93; &lt; aList&#91;k&#93;:
       swapList(aList, k, minIndex)
       swapList(aList, k, minIndex)
   else:# aList[maxIndex] &gt; aList[minIndex]:
   else:# aList&#91;maxIndex&#93; &gt; aList&#91;minIndex&#93;:
     swapList(aList, maxIndex, minIndex)
     swapList(aList, maxIndex, minIndex)
   return getMedian(aList)
   return getMedian(aList)
   
   
  def swapList(aList, one, another):
  def swapList(aList, one, another):
   aList[one], aList[another] = aList[another], aList[one]
   aList&#91;one&#93;, aList&#91;another&#93; = aList&#91;another&#93;, aList&#91;one&#93;
    
    
  def factorial(n):
  def factorial(n):
Line 52: Line 50:
   import sys, math
   import sys, math
   if len(sys.argv) &gt; 2 :
   if len(sys.argv) &gt; 2 :
     if sys.argv[2] == "metric":
     if sys.argv&#91;2&#93; == "metric":
       for i in range(1, int(sys.argv[1])):
       for i in range(1, int(sys.argv&#91;1&#93;)):
         print i, metric(i), i**2, i*math.log(i)
         print i, metric(i), i**2, i*math.log(i)
     elif sys.argv[2] == "median":
     elif sys.argv&#91;2&#93; == "median":
       test= range(int(sys.argv[1]))
       test= range(int(sys.argv&#91;1&#93;))
       test.reverse()
       test.reverse()
       print getMedian(test)
       print getMedian(test)
     elif sys.argv[2] == "sort":
     elif sys.argv&#91;2&#93; == "sort":
       test= range(int(sys.argv[1]))
       test= range(int(sys.argv&#91;1&#93;))
       test.reverse()
       test.reverse()
       test.sort()
       test.sort()
       print test[len(test)/2]
       print test&#91;len(test)/2&#93;


= Using Swap ver.2 =
= Using Swap ver.2 =
Line 70: Line 68:
  def getMedian(aList):
  def getMedian(aList):
   if len(aList) &lt; 3:
   if len(aList) &lt; 3:
     return aList[start]
     return aList&#91;start&#93;
   n = len(aList)-1
   n = len(aList)-1
   k = n/2
   k = n/2
   for i in range(k):
   for i in range(k):
     maxIndex = aList.index(max(aList[0:k-i]))
     maxIndex = aList.index(max(aList&#91;0:k-i&#93;))
     minIndex = aList.index(min(aList[k+1+i:n+1]))
     minIndex = aList.index(min(aList&#91;k+1+i:n+1&#93;))
     swapList(aList, k-1-i, maxIndex)
     swapList(aList, k-1-i, maxIndex)
     swapList(aList, k+1+i, minIndex)
     swapList(aList, k+1+i, minIndex)
     if aList[maxIndex] &lt;= aList[k] &lt;= aList[minIndex]:
     if aList&#91;maxIndex&#93; &lt;= aList&#91;k&#93; &lt;= aList&#91;minIndex&#93;:
       return aList[k]
       return aList&#91;k&#93;
     elif aList[maxIndex] &lt;= aList[minIndex]:
     elif aList&#91;maxIndex&#93; &lt;= aList&#91;minIndex&#93;:
       if aList[maxIndex] &gt; aList[k]:
       if aList&#91;maxIndex&#93; &gt; aList&#91;k&#93;:
         swapList(aList, k, maxIndex)
         swapList(aList, k, maxIndex)
       elif aList[minIndex] &lt; aList[k]:
       elif aList&#91;minIndex&#93; &lt; aList&#91;k&#93;:
         swapList(aList, k, minIndex)
         swapList(aList, k, minIndex)
     else:# aList[maxIndex] &gt; aList[minIndex]:
     else:# aList&#91;maxIndex&#93; &gt; aList&#91;minIndex&#93;:
       swapList(aList, maxIndex, minIndex)
       swapList(aList, maxIndex, minIndex)
   
   
  def swapList(aList, one, another):
  def swapList(aList, one, another):
   aList[one], aList[another] = aList[another], aList[one]
   aList&#91;one&#93;, aList&#91;another&#93; = aList&#91;another&#93;, aList&#91;one&#93;
    
    
  def factorial(n):
  def factorial(n):
Line 108: Line 106:
   import sys, math
   import sys, math
   if len(sys.argv) &gt; 2 :
   if len(sys.argv) &gt; 2 :
     if sys.argv[2] == "metric":
     if sys.argv&#91;2&#93; == "metric":
       print "n\ttime\tn*n\tnlogn"
       print "n\ttime\tn*n\tnlogn"
       for i in range(1, int(sys.argv[1])):
       for i in range(1, int(sys.argv&#91;1&#93;)):
         print i,'\t', metric(i), '\t',i**2, '\t', i*math.log(i)
         print i,'\t', metric(i), '\t',i**2, '\t', i*math.log(i)
     elif sys.argv[2] == "median":
     elif sys.argv&#91;2&#93; == "median":
       test= range(int(sys.argv[1]))
       test= range(int(sys.argv&#91;1&#93;))
       test.reverse()
       test.reverse()
       print getMedian(test)
       print getMedian(test)
     elif sys.argv[2] == "sort":
     elif sys.argv&#91;2&#93; == "sort":
       test= range(int(sys.argv[1]))
       test= range(int(sys.argv&#91;1&#93;))
       test.reverse()
       test.reverse()
       test.sort()
       test.sort()
       print test[len(test)/2]
       print test&#91;len(test)/2&#93;

Latest revision as of 12:46, 27 March 2026

Using Swap ver.1

Time Complexity: 2k* (k!)2/ 2k! Sigmai=1 to k ( i+1 ) ( k C i ) 2 approximation: O( n2 ) 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 

#!/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. 

#!/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]
Retrieved from "https://mediawiki.zeropage.org/index.php?title=중위수구하기/나휘동&oldid=87339"
Last modified
This page was last edited on 27 March 2026, at 12:46.