Property |
Value |
dbo:abstract
|
- クイックセレクト(英: quickselect)は配列内の k 番目に小さい要素を見つけるための選択アルゴリズム。クイックソートによく似たアルゴリズムで、クイックソートと同じくアントニー・ホーアに発見されたため、 ホーアの選択アルゴリズムとも呼ばれる。 クイックソートと同様に、平均的なパフォーマンスは良好だが、最悪の場合のパフォーマンスは悪くなる。クイックセレクトとその派生アルゴリズムは、効率的な実装として最もよく使われる選択アルゴリズムである。 クイックセレクトは、クイックソートと同じように1つの要素をピボットとして選択し、ピボットに基づいてデータをピボットよりも小さいかに大きいか二分割するのを繰り返す。ただし、クイックソートのように分割した両方の区間に対して再帰するのではなく、クイックセレクトは一方の側、つまり検索している要素のある側にのみ再帰する。これにより、平均計算量が軽減される。平均計算量はクイックソートが なのに対してクイックセレクトは 。最悪計算量はクイックソートと同じく 。 クイックソートと同様に、クイックセレクトは通常、In-placeアルゴリズムとして実装され、 k 番目の要素を選択するだけでなく、データを部分的にソートする。ソートとの関係の詳細については、選択アルゴリズムを参照。 (ja)
- クイックセレクト(英: quickselect)は配列内の k 番目に小さい要素を見つけるための選択アルゴリズム。クイックソートによく似たアルゴリズムで、クイックソートと同じくアントニー・ホーアに発見されたため、 ホーアの選択アルゴリズムとも呼ばれる。 クイックソートと同様に、平均的なパフォーマンスは良好だが、最悪の場合のパフォーマンスは悪くなる。クイックセレクトとその派生アルゴリズムは、効率的な実装として最もよく使われる選択アルゴリズムである。 クイックセレクトは、クイックソートと同じように1つの要素をピボットとして選択し、ピボットに基づいてデータをピボットよりも小さいかに大きいか二分割するのを繰り返す。ただし、クイックソートのように分割した両方の区間に対して再帰するのではなく、クイックセレクトは一方の側、つまり検索している要素のある側にのみ再帰する。これにより、平均計算量が軽減される。平均計算量はクイックソートが なのに対してクイックセレクトは 。最悪計算量はクイックソートと同じく 。 クイックソートと同様に、クイックセレクトは通常、In-placeアルゴリズムとして実装され、 k 番目の要素を選択するだけでなく、データを部分的にソートする。ソートとの関係の詳細については、選択アルゴリズムを参照。 (ja)
|
dbo:thumbnail
| |
dbo:wikiPageExternalLink
| |
dbo:wikiPageID
| |
dbo:wikiPageLength
|
- 6040 (xsd:nonNegativeInteger)
|
dbo:wikiPageRevisionID
| |
dbo:wikiPageWikiLink
| |
prop-ja:caption
|
- クイックセレクトの可視化。22番目に小さい要素を選択する (ja)
- クイックセレクトの可視化。22番目に小さい要素を選択する (ja)
|
prop-ja:class
| |
prop-ja:data
| |
prop-ja:name
|
- クイックセレクト (ja)
- クイックセレクト (ja)
|
prop-ja:optimal
| |
prop-ja:time
| |
prop-ja:wikiPageUsesTemplate
| |
dct:subject
| |
rdfs:comment
|
- クイックセレクト(英: quickselect)は配列内の k 番目に小さい要素を見つけるための選択アルゴリズム。クイックソートによく似たアルゴリズムで、クイックソートと同じくアントニー・ホーアに発見されたため、 ホーアの選択アルゴリズムとも呼ばれる。 クイックソートと同様に、平均的なパフォーマンスは良好だが、最悪の場合のパフォーマンスは悪くなる。クイックセレクトとその派生アルゴリズムは、効率的な実装として最もよく使われる選択アルゴリズムである。 クイックセレクトは、クイックソートと同じように1つの要素をピボットとして選択し、ピボットに基づいてデータをピボットよりも小さいかに大きいか二分割するのを繰り返す。ただし、クイックソートのように分割した両方の区間に対して再帰するのではなく、クイックセレクトは一方の側、つまり検索している要素のある側にのみ再帰する。これにより、平均計算量が軽減される。平均計算量はクイックソートが なのに対してクイックセレクトは 。最悪計算量はクイックソートと同じく 。 クイックソートと同様に、クイックセレクトは通常、In-placeアルゴリズムとして実装され、 k 番目の要素を選択するだけでなく、データを部分的にソートする。ソートとの関係の詳細については、選択アルゴリズムを参照。 (ja)
- クイックセレクト(英: quickselect)は配列内の k 番目に小さい要素を見つけるための選択アルゴリズム。クイックソートによく似たアルゴリズムで、クイックソートと同じくアントニー・ホーアに発見されたため、 ホーアの選択アルゴリズムとも呼ばれる。 クイックソートと同様に、平均的なパフォーマンスは良好だが、最悪の場合のパフォーマンスは悪くなる。クイックセレクトとその派生アルゴリズムは、効率的な実装として最もよく使われる選択アルゴリズムである。 クイックセレクトは、クイックソートと同じように1つの要素をピボットとして選択し、ピボットに基づいてデータをピボットよりも小さいかに大きいか二分割するのを繰り返す。ただし、クイックソートのように分割した両方の区間に対して再帰するのではなく、クイックセレクトは一方の側、つまり検索している要素のある側にのみ再帰する。これにより、平均計算量が軽減される。平均計算量はクイックソートが なのに対してクイックセレクトは 。最悪計算量はクイックソートと同じく 。 クイックソートと同様に、クイックセレクトは通常、In-placeアルゴリズムとして実装され、 k 番目の要素を選択するだけでなく、データを部分的にソートする。ソートとの関係の詳細については、選択アルゴリズムを参照。 (ja)
|
rdfs:label
|
- クイックセレクト (ja)
- クイックセレクト (ja)
|
prov:wasDerivedFrom
| |
foaf:depiction
| |
foaf:isPrimaryTopicOf
| |
is dbo:wikiPageWikiLink
of | |
is owl:sameAs
of | |
is foaf:primaryTopic
of | |