私はこのペーパーProduct quantization for nearest neighbor searchを読んでいます。表IIページ5の最終行に近似時間近似近似
は
を与えるkの最小要素 を検索するため、この表に示さ複雑 は、n >> kおよび場合 要素があるの平均複雑です任意
n+klogkloglognある
を命じました。
私たちはO(n)でソートされていないのk最近傍を取得するために、線形選択アルゴリズムを使用し、O(klogk)とkの最近傍を並べ替えることができますね、私たちは、合計でO(n+klogk)を持つことができます。しかし、loglognの用語はどこから来たのですか？
この論文はこれに関するTAOCPの本を参照していますが、私はこの本を手にしていません。
最初に、表IIは各ステップの複雑さをレポートします。したがって、ADCの複雑さを測定するためにすべての用語を追加する必要があります。テーブルの最後の行に
、それは両方でSDCとADC、のための単一の複雑さ：
N + KログKログログN
用語に対応ドナルド・クヌスの本[25]からコピー/ペーストされたn個の変数のセット中のk個の最小値を見つけるために採用する選択アルゴリズムの平均アルゴリズムコスト。
私は手で本を持っていないので、私は確認できませんが、それは正しいと思います。著者
ありがとう、私はそれがどのようにADCのケースで 'loglogn'になるのかよく分かりませんが、ちょっと説明してください。ありがとう！ – dontloo
私の更新@dontlooを見てください。新しい質問がある場合は、それだけで十分です。新しい質問を投稿してください。 :) – gsamaras
私は混乱しているところですが、明らかにしていただきありがとうございます。私が得ることができるこの式に最も近い形式である 'n + k log k'を意味することができます。とにかく、ありがとう、私はこのペーパーの文脈を超えてより明確な質問を投稿するつもりだと思う。 – dontloo
から
それだけでは不十分なテーブルの書式と思われます。 「k番目の最小距離を見つける」とは、SDCではn + k log k、ADCでは「log log n」です。列がお互いに近すぎるので、それらを一緒に 'n + k log k log log n' – user31264
@ user31264として読んでください！私もそれについて考えていましたが、 'log log n'という時間の複雑さは、私にはあまり意味がありません。 – dontloo
@ user31264とdontloo、あなたは私の[質問]（http://stackoverflow.com/questions/38382217/k-reproduction-values）を見てみることができますか？ – gsamaras