Averages/Median: Difference between revisions
Content added Content deleted
No edit summary |
(task description: Improve formatting and add related tasks box) |
||
Line 1: | Line 1: | ||
{{task|Probability and statistics}} |
{{task|Probability and statistics}} |
||
{{task heading}} |
|||
Write a program to find the [[wp:Median|median]] value of a vector of floating-point numbers. |
Write a program to find the [[wp:Median|median]] value of a vector of floating-point numbers. |
||
Line 7: | Line 9: | ||
There are several approaches to this. One is to sort the elements, and then pick the one(s) in the middle. Sorting would take at least <span style="font-family: serif">O(''n'' log''n'')</span>. Another would be to build a priority queue from the elements, and then extract half of the elements to get to the middle one(s). This would also take <span style="font-family: serif">O(''n'' log''n'')</span>. The best solution is to use the [[wp:Selection algorithm|selection algorithm]] to find the median in <span style="font-family: serif">O(''n'')</span> time. |
There are several approaches to this. One is to sort the elements, and then pick the one(s) in the middle. Sorting would take at least <span style="font-family: serif">O(''n'' log''n'')</span>. Another would be to build a priority queue from the elements, and then extract half of the elements to get to the middle one(s). This would also take <span style="font-family: serif">O(''n'' log''n'')</span>. The best solution is to use the [[wp:Selection algorithm|selection algorithm]] to find the median in <span style="font-family: serif">O(''n'')</span> time. |
||
{{task heading|See also}} |
|||
{{Related tasks/Statistical measures}} |
|||
<hr> |
|||
;Related tasks: |
|||
:* [[Mean]] |
|||
:* [[Mode]] |
|||
<br><br> |
|||
=={{header|Ada}}== |
=={{header|Ada}}== |