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
我靠,又是海星写的,无处不在啊!