2。一堆数在一个集合中，总共2n个，问如何将这些数分成A，B两分，每分n个，要求A中的数均小于B中的数，需要考虑时间复杂度，答案是 求中位数，时间为O（n），请牛人解释一下。谢谢
4 个解决方案
#1
利用对手论证法证明中位数问题的比较次数下界
作者:starfish 时间:2002-01-05 11:59 出处:互联网 责编:chinaitpower
摘要：利用对手论证法证明中位数问题的比较次数下界
5个数通过6次比较求中位数的方法如下：
5个数之间的大小关系构成的一个树形图T。T中的一个结点代表一个数，而一条边代表它所关联的两个数的大小关系，T的根就是中位数。显然T中的一条边要由一次比赛来确定。在下面的图中，如果x大于y，则节点x在节点y的上方且x和y有一条边相连。另外，*表示一般的数，o表示下一次即将进行比较的两个数。
第1步，先任取两个数比较，结果为：
*
|
* o o *
第2步，再取另外两个数比较，结果为：
o o
| |
* * *
第3步，按照上图比较其中两个标记为o的数，比较结果只有一种情况：
*
/ \
* o
|
* o
第4步，按照上图比较其中两个标记为o的数，比较结果有两种情况：
* o *
/ \ / / \
o * o o
| | |
* * *
第5步，按照上图比较其中两个标记为o的数，比较结果有两种情况：
* * *
/ \ / \ /
/ \/ \ /
| /\ | /
| / \ | *
| / \ | | \
|/ \| | \
o o | \
| o o
| |
| |
* *
第6步，按照上图比较其中两个标记为o的数，比较结果有两种情况：
* * * * * *
\ / \ / | |
x x * *
| / \ | |
* * * x x
| | / \
* * * *
|
*
其中的x就是中位数。
事实上，可以证明：对于n个数求中位数，至少需要3(n-1)/2次比较，并且存在一个O(n)次比较的算法。
下面介绍如何利用对手论证方法来证明中位数问题的比较次数下界。
首先介绍“对手论证（Adversary Argument）”方法。
若用P表示所讨论的问题，I表示问题的输入，A表示求解问题P的基于比较运算的算法T(A,I)表示对于输入I算法A的计算时间复杂性，那么，函数
U(n)=min{max{T(A,I)}, for each I}, for each A，
是问题P当输入的大小为n时在最坏情况下的最好下界。它是问题所固有的。
问题P的这个最好下界通常很难按其定义计算得到，因为对于一个具体的A，要得到
max{T(A,I)}, for each I
就是一件很难的事，更何况对于一切的A。因此，人们往往不去精确地求U(n)，而是退而求其次，即找一个f(n)，它不大于U(n)但尽量地接近于U(n)，使f(n)成为问题P的一个好下界。
作者:starfish 时间:2002-01-05 11:59 出处:互联网 责编:chinaitpower
摘要：利用对手论证法证明中位数问题的比较次数下界
5个数通过6次比较求中位数的方法如下：
5个数之间的大小关系构成的一个树形图T。T中的一个结点代表一个数，而一条边代表它所关联的两个数的大小关系，T的根就是中位数。显然T中的一条边要由一次比赛来确定。在下面的图中，如果x大于y，则节点x在节点y的上方且x和y有一条边相连。另外，*表示一般的数，o表示下一次即将进行比较的两个数。
第1步，先任取两个数比较，结果为：
*
|
* o o *
第2步，再取另外两个数比较，结果为：
o o
| |
* * *
第3步，按照上图比较其中两个标记为o的数，比较结果只有一种情况：
*
/ \
* o
|
* o
第4步，按照上图比较其中两个标记为o的数，比较结果有两种情况：
* o *
/ \ / / \
o * o o
| | |
* * *
第5步，按照上图比较其中两个标记为o的数，比较结果有两种情况：
* * *
/ \ / \ /
/ \/ \ /
| /\ | /
| / \ | *
| / \ | | \
|/ \| | \
o o | \
| o o
| |
| |
* *
第6步，按照上图比较其中两个标记为o的数，比较结果有两种情况：
* * * * * *
\ / \ / | |
x x * *
| / \ | |
* * * x x
| | / \
* * * *
|
*
其中的x就是中位数。
事实上，可以证明：对于n个数求中位数，至少需要3(n-1)/2次比较，并且存在一个O(n)次比较的算法。
下面介绍如何利用对手论证方法来证明中位数问题的比较次数下界。
首先介绍“对手论证（Adversary Argument）”方法。
若用P表示所讨论的问题，I表示问题的输入，A表示求解问题P的基于比较运算的算法T(A,I)表示对于输入I算法A的计算时间复杂性，那么，函数
U(n)=min{max{T(A,I)}, for each I}, for each A，
是问题P当输入的大小为n时在最坏情况下的最好下界。它是问题所固有的。
问题P的这个最好下界通常很难按其定义计算得到，因为对于一个具体的A，要得到
max{T(A,I)}, for each I
就是一件很难的事，更何况对于一切的A。因此，人们往往不去精确地求U(n)，而是退而求其次，即找一个f(n)，它不大于U(n)但尽量地接近于U(n)，使f(n)成为问题P的一个好下界。
#2
请不要发表可能给我们带来伤害的言论，谢谢配合
什么垃圾论坛啊
连个学术论文都紧张成这样
不发了
什么垃圾论坛啊
连个学术论文都紧张成这样
不发了
#3
http://www.chinaitpower.net/A/2002-01-05/10026.html
#4
我靠,又是海星写的,无处不在啊!
#1
利用对手论证法证明中位数问题的比较次数下界
作者:starfish 时间:2002-01-05 11:59 出处:互联网 责编:chinaitpower
摘要：利用对手论证法证明中位数问题的比较次数下界
5个数通过6次比较求中位数的方法如下：
5个数之间的大小关系构成的一个树形图T。T中的一个结点代表一个数，而一条边代表它所关联的两个数的大小关系，T的根就是中位数。显然T中的一条边要由一次比赛来确定。在下面的图中，如果x大于y，则节点x在节点y的上方且x和y有一条边相连。另外，*表示一般的数，o表示下一次即将进行比较的两个数。
第1步，先任取两个数比较，结果为：
*
|
* o o *
第2步，再取另外两个数比较，结果为：
o o
| |
* * *
第3步，按照上图比较其中两个标记为o的数，比较结果只有一种情况：
*
/ \
* o
|
* o
第4步，按照上图比较其中两个标记为o的数，比较结果有两种情况：
* o *
/ \ / / \
o * o o
| | |
* * *
第5步，按照上图比较其中两个标记为o的数，比较结果有两种情况：
* * *
/ \ / \ /
/ \/ \ /
| /\ | /
| / \ | *
| / \ | | \
|/ \| | \
o o | \
| o o
| |
| |
* *
第6步，按照上图比较其中两个标记为o的数，比较结果有两种情况：
* * * * * *
\ / \ / | |
x x * *
| / \ | |
* * * x x
| | / \
* * * *
|
*
其中的x就是中位数。
事实上，可以证明：对于n个数求中位数，至少需要3(n-1)/2次比较，并且存在一个O(n)次比较的算法。
下面介绍如何利用对手论证方法来证明中位数问题的比较次数下界。
首先介绍“对手论证（Adversary Argument）”方法。
若用P表示所讨论的问题，I表示问题的输入，A表示求解问题P的基于比较运算的算法T(A,I)表示对于输入I算法A的计算时间复杂性，那么，函数
U(n)=min{max{T(A,I)}, for each I}, for each A，
是问题P当输入的大小为n时在最坏情况下的最好下界。它是问题所固有的。
问题P的这个最好下界通常很难按其定义计算得到，因为对于一个具体的A，要得到
max{T(A,I)}, for each I
就是一件很难的事，更何况对于一切的A。因此，人们往往不去精确地求U(n)，而是退而求其次，即找一个f(n)，它不大于U(n)但尽量地接近于U(n)，使f(n)成为问题P的一个好下界。
作者:starfish 时间:2002-01-05 11:59 出处:互联网 责编:chinaitpower
摘要：利用对手论证法证明中位数问题的比较次数下界
5个数通过6次比较求中位数的方法如下：
5个数之间的大小关系构成的一个树形图T。T中的一个结点代表一个数，而一条边代表它所关联的两个数的大小关系，T的根就是中位数。显然T中的一条边要由一次比赛来确定。在下面的图中，如果x大于y，则节点x在节点y的上方且x和y有一条边相连。另外，*表示一般的数，o表示下一次即将进行比较的两个数。
第1步，先任取两个数比较，结果为：
*
|
* o o *
第2步，再取另外两个数比较，结果为：
o o
| |
* * *
第3步，按照上图比较其中两个标记为o的数，比较结果只有一种情况：
*
/ \
* o
|
* o
第4步，按照上图比较其中两个标记为o的数，比较结果有两种情况：
* o *
/ \ / / \
o * o o
| | |
* * *
第5步，按照上图比较其中两个标记为o的数，比较结果有两种情况：
* * *
/ \ / \ /
/ \/ \ /
| /\ | /
| / \ | *
| / \ | | \
|/ \| | \
o o | \
| o o
| |
| |
* *
第6步，按照上图比较其中两个标记为o的数，比较结果有两种情况：
* * * * * *
\ / \ / | |
x x * *
| / \ | |
* * * x x
| | / \
* * * *
|
*
其中的x就是中位数。
事实上，可以证明：对于n个数求中位数，至少需要3(n-1)/2次比较，并且存在一个O(n)次比较的算法。
下面介绍如何利用对手论证方法来证明中位数问题的比较次数下界。
首先介绍“对手论证（Adversary Argument）”方法。
若用P表示所讨论的问题，I表示问题的输入，A表示求解问题P的基于比较运算的算法T(A,I)表示对于输入I算法A的计算时间复杂性，那么，函数
U(n)=min{max{T(A,I)}, for each I}, for each A，
是问题P当输入的大小为n时在最坏情况下的最好下界。它是问题所固有的。
问题P的这个最好下界通常很难按其定义计算得到，因为对于一个具体的A，要得到
max{T(A,I)}, for each I
就是一件很难的事，更何况对于一切的A。因此，人们往往不去精确地求U(n)，而是退而求其次，即找一个f(n)，它不大于U(n)但尽量地接近于U(n)，使f(n)成为问题P的一个好下界。
#2
请不要发表可能给我们带来伤害的言论，谢谢配合
什么垃圾论坛啊
连个学术论文都紧张成这样
不发了
什么垃圾论坛啊
连个学术论文都紧张成这样
不发了
#3
http://www.chinaitpower.net/A/2002-01-05/10026.html
#4
我靠,又是海星写的,无处不在啊!