| dbo:abstract
|
- Batcher's odd–even mergesortis a generic construction devised by Ken Batcher for sorting networks of size O(n (log n)2) and depth O((log n)2), where n is the number of items to be sorted. Although it is not asymptotically optimal, Knuth concluded in 1998, with respect to the AKS network that "Batcher's method is much better, unless n exceeds the total memory capacity of all computers on earth!" It is popularized by the second book, as an easy way of doing reasonably efficient sorts on graphics-processing hardware. (en)
- バッチャー奇偶マージソート(英: Batcher's odd–even mergesort) は Ken Batche(en:Ken Batcher) によって考案された、要素数nに対して、大きさ O(n (log n)2) かつ深さ O((log n)2) のソーティングネットワークである。これは（en:asymptotically optimal algorithm）ではないものの、ドナルド・クヌースは1998年、 AKSネットワークに関して「n が地球上の全てのコンピュータのメモリの全てに収まり切らないほど大きくない限り、Batcheの方法のほうが (AKSネットワークよりも) 優れている。」と言った。the second GPU Gems bookの中で、効率的なグラフィックスプロセスハードウェアによるソートの簡単な実装法として紹介されたことにより有名になった。 (ja)
- Batcher排序网络是由一系列Batcher比较器（Batcher's Comparator）组成的。Batcher比较器是指在两个输入端给定输入x,y，再在两个输出端输出最大值max{x,y}和最小值min{x,y}。 比较器网络是用Batcher比较器连成的完成某一功能的网络。 所谓双调序列（Bitonic Sequence）是指由一个非严格增序列X和非严格减序列Y（其中X的最小元素正好是Y的最大元素）构成的序列，比如序列（23,10,8,3,5,7,11,78）。 定义：一个序列a1,a2,…,an是双调序列（Bitonic Sequence），如果： 1.
* 存在一个ak(1≤k≤n),使得a1≥…≥ak≤…≤an成立；或者 2.
* 序列能够循环移位满足条件（1） (zh)
|
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 3435 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:averageTime
| |
| dbp:bestTime
| |
| dbp:caption
|
- Visualization of the odd–even mergesort network with eight inputs (en)
|
| dbp:class
| |
| dbp:data
| |
| dbp:optimal
| |
| dbp:space
| |
| dbp:time
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdf:type
| |
| rdfs:comment
|
- Batcher's odd–even mergesortis a generic construction devised by Ken Batcher for sorting networks of size O(n (log n)2) and depth O((log n)2), where n is the number of items to be sorted. Although it is not asymptotically optimal, Knuth concluded in 1998, with respect to the AKS network that "Batcher's method is much better, unless n exceeds the total memory capacity of all computers on earth!" It is popularized by the second book, as an easy way of doing reasonably efficient sorts on graphics-processing hardware. (en)
- バッチャー奇偶マージソート(英: Batcher's odd–even mergesort) は Ken Batche(en:Ken Batcher) によって考案された、要素数nに対して、大きさ O(n (log n)2) かつ深さ O((log n)2) のソーティングネットワークである。これは（en:asymptotically optimal algorithm）ではないものの、ドナルド・クヌースは1998年、 AKSネットワークに関して「n が地球上の全てのコンピュータのメモリの全てに収まり切らないほど大きくない限り、Batcheの方法のほうが (AKSネットワークよりも) 優れている。」と言った。the second GPU Gems bookの中で、効率的なグラフィックスプロセスハードウェアによるソートの簡単な実装法として紹介されたことにより有名になった。 (ja)
- Batcher排序网络是由一系列Batcher比较器（Batcher's Comparator）组成的。Batcher比较器是指在两个输入端给定输入x,y，再在两个输出端输出最大值max{x,y}和最小值min{x,y}。 比较器网络是用Batcher比较器连成的完成某一功能的网络。 所谓双调序列（Bitonic Sequence）是指由一个非严格增序列X和非严格减序列Y（其中X的最小元素正好是Y的最大元素）构成的序列，比如序列（23,10,8,3,5,7,11,78）。 定义：一个序列a1,a2,…,an是双调序列（Bitonic Sequence），如果： 1.
* 存在一个ak(1≤k≤n),使得a1≥…≥ak≤…≤an成立；或者 2.
* 序列能够循环移位满足条件（1） (zh)
|
| rdfs:label
|
- Batcher odd–even mergesort (en)
- 배처 홀짝 병합 정렬 (ko)
- バッチャー奇偶マージソート (ja)
- Batcher归并网络 (zh)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
