複雑さの解析でlog（k）とlog（n）の違いを理解できない。k <nのアルゴリズム実行時のlog（n）対log（k）
私はサイズnの配列を持っています。私はアルゴリズムの入力である別の番号k <を持っています（したがって、あらかじめ既知の定数ではありません）。 log（n）対log（k）の複雑さを持つアルゴリズムの例は何ですか？私はlog（n）の複雑さを持つアルゴリズムしか考えられません。
たとえば、mergesortは実行時分析（O（nlogn））でlog（n）の複雑さを持ちます。
あなたのアルゴリズムは、サイズn及び大きk < nの数のリストを取る場合、入力サイズは（kはnの同じ漸近オーダーであると仮定して）n + log(k)のオーダーです。どうして？ kは、プレース・バリュー・システム（例えば、2進数または10進数）で表される数字であり、数はkで、log k桁の数字が必要です。
したがって、あなたのアルゴリズムが入力kを受け取り、すべての数字を使用またはチェックする必要があるような方法で使用すると（たとえば等価がチェックされているなど）、アルゴリズム全体の複雑さは少なくともlog kのオーダー。番号で複雑なことをすると、複雑さはさらに高くなる可能性があります。たとえば、for i = 1 to k do ...のようなものがある場合、log kビットの数字k（ただし、iは多くの/ほとんどの値に対してkよりも少ないビットを使用しますが、アルゴリズムの複雑さは少なくともk - 多分高くなります。 i、塩基に依存する）。
O（log k）という用語が出現する可能性のある箇所については、「ワンサイズの説明」はありません。
このランタイムは、シーケンスの小さな部分のみを並べ替える必要がある場合に、検索とソートのアルゴリズムで発生することがあります。例えば、C++標準ライブラリのstd::partial_sort関数は、最初のk要素がソートされた順序で残りが時間O（n log k）で任意の順序になるように順序を並べ替えます。これを実装できる方法の1つは、最大でkのサイズのmin-heapを維持し、n回の挿入/削除を実行することです。これはそれぞれが時間O（log k）を要するn回の操作です。同様に、最大k個の要素の最大ヒープを維持することによって動作する、データストリーム内のk個の最大要素を見つけるためのO（n log k）時間アルゴリズムがあります。
（どちらの方法も最適ではありませんが、リニア時間選択アルゴリズムを使用して時間O（n + k log k）で部分ソートを行うことができ、同様にデータストリームの上位k要素をO（n）。）m
このランタイムは、問題のサイズが入力サイズのいくつかのパラメータに依存する分割および征服戦略を含むアルゴリズムで表示されることがあります。例えば、凸包を計算するためのKirkpatrick-Seidel algorithmは、再帰でレベルごとに線形演算を行い、層の数はO（log k）であり、kは結果として得られる凸包内の要素の数です。総仕事量はO（n log k）となり、出力に敏感なアルゴリズムになります。
場合によっては、一度に1桁の要素のコレクションを処理するため、O（log k）という用語が発生することがあります。例えば、radix sortは、0からkまでの範囲のn値をソートするために使用されるときに実行時間がO（n log k）であり、log k項はその数にO（log k）桁があることから生じるk。
グラフのアルゴリズムでは、エッジ数（m）はノード数（n）に関係しますが、ノード数（n）とは無関係ですが、O（m log n）のようなランタイムがよく見られます。 implement Dijkstra's algorithm with a binary heap。