Introduction
代写一个算法来解决一个问题。这个作业比较有意思的是，给了你一个时间复杂度较高的算法，然后让你实现一个更快的算法，越快越好。
Requirement
Implement an algorithm that partitions an unsorted array of n floats into two
nonempty subarrays L and R so that all of the elements of L are less than or
equal to those in R and min(R) – max(L) is as large as possible. You can think
of this as a kind of 1-dimensional clustering problem in which we want to have
two clusters separated by as large a distance as possible.
The simplest nontrivial algorithm for this problem involves sorting the n
numbers and then identifying the consecutive elements that are farthest apart.
This has an overall time complexity of O(n log(n)). As we discussed in class,
this problem can be solved optimally in O(n) of time. For this assignment you
will implement a routine that partitions the array in O(n) time so that the k
elements of L are in the left subarray, the n-k elements of R are in the right
subarray, and elements a[k] and a[k-1] are the two most widely-separated
elements that define the separation between L and R.
Specification: int partition(float a[], int n)
Pre Condition: The unsorted array a[ ] contains n floats.
Post Condition: The array is partitioned into left subarray L = a[0]…a[k],
with a[i] < a[k] for 0 < i < k, and right subarray R = a[k+1]…a[n-1], with
a[i] < a[n-1] for k < i < n. The return value is the index k.
In words, elements 0 to k represent the left subarray, elements k+1 to n-1
represent the right subarray, and a[k] is the largest key in the left subarray
and a[k+1] is the smallest key in the right subarray, i.e., a[k+1] - a[k] is
the separation between the two subarrays/clusters. The critical condition, of
course, is that this separation must be the maximum possible. As we discussed
in class, binning allows the widest-separation problem to be solved in O(n)
time.
Detail
- Your implemented routine must be correct and have O(n) run-time complexity.
- You must provide empirical evidence that your routine does in fact have O(n) complexity. This requires the running of many tests for increasing values of n to produce plots showing that the running time of your routine is proportional to n. To further show that your routine scales better than O(n log(n)) you must compare its running time to an implementation that uses sorting to solve the problem. I recommend that you write a testing program that runs these tests for n=512, 1K, 2K, … 16K (or more if necessary) so that you can clearly distinguish O(n) complexity from O(n log(n)) complexity. You may find that there is significant variance in the running times for smaller values of n so it may be necessary to average several runs at those values.
You should produce decent-looking code with reasonable documentation,
including references to any outside sources (e.g., books, code obtained on the
web, etc.) that you used. Your submission will consist of a PDF report with
your test results/plots and conclusions. All of the code used for the report
will be included in an appendix.
Suggestions
The testing will likely take significantly more time than the writing of the
partition routine so plan your time accordingly. I strongly recommend that you
start as early as possible so that you can ask questions during class periods
prior to the due date. You definitely don’t want to wait until the last
minute!
