このアルゴリズムのBig-Oを決定する

Question

Big-Oが以下のコードであることを理解しようとしています。コードは基本的に

行うことになっている何

、私はランダムなノードのサブセット（最大サイズ= selectionSize）と、それらの間に存在するすべてのエッジを選択しようとしています。ランダムノードの選択は、whileループで行われます。それをした後、私は選択されたノードの間に存在するエッジを選択したい。

は、私はそれが

は私が実行している時間がO = n^2n=selectionSizeだと思う理由&と思われるもの。理由は、nodesの要素のサイズを増やすことはできますが（たとえば10000にするなど）、最大でselectionSizeまでしかループしないため、アルゴリズムに影響するとは思われません。私がこれが間違っていることを少し心配している唯一の理由は、whileループのためですこれは（ランダムなので）かなり時間がかかることがありますが、時間的には全体の出力には影響しないと思います。 編集：（node.getNeighbors()はnodesのほとんどのサイズにすることができるため）考え直し上うわ...ネヴァーマインド... nodesサイズがそれに影響を与えない...だから私はselectionSizeはと等しい場合だと思いますnodesのサイズ、実行時間はO=n^2、n=size of nodesです。

ヒント/ヒントをお待ちしております。

コード

// nodes and selectionSize are my input: 
int[] nodes = {1,2,3...,1000}; // 1000 elements 
int selectionSize = 500; // This can be at most the size of the elements (in this case 1000) 

run_algo(nodes, selectionSize); 

public void run_algo(int[] nodes, int selectionSize) { 
    randomNodesList = {}; 

    while(randomNodesList < selectionSize) { 
     randomNode = selectRandomNode(nodes); // Assume O(1) 

     if(!randomNodesList.exists(randomNode)) { // Assume O(1) 
      randomNodesList.push_back(randomNode); // Assume O(1) 
     } 
    } 

    foreach(node in randomNodesList) { 
     foreach(neighbor in node.getNeighbors()) { // Max. nodes size (in this case 1000) 
      if (!randomNodesList.exists(neighbor)) { // Assume O(1) 
       AddEdge(node, neighbor); // Takes O(1) time 
      } 
     } 
    } 
} 

Answer 1

selectRandomNode(nodes);かの作品は（同じノードが二回撮像することができる）、そして大きなoは、not definedです。

交換せずに動作する場合は、O(n^2)です（最悪の場合、すべてのノードが他のすべてのノードに接続されている可能性があります）。交換せずに選択する上

---

注：

• あなたが大きnの配列を与えられている場合を考えてみましょう、Aと空の配列、Bを言います。 Aのすべての要素は一意です。

• Bをnの要素でランダムに選択して入力します。Aからランダムに選択します。 Bに少なくともk個のユニークな要素があることが望まれます。

それ以上kユニークなアイテムを有する確率がn（Iプロット後に式を追加した）の増加と共に増加することを示すことができます。

したがって、実際には、単一パス（即ち未満nステップ）におけるループ仕上げの確率がnとk増加の差として大きくなります。 これについて考えると非常に直感的です。数学はちょうど上の桜です。

---

def k_numerator(n, k): 
    res = 0 
    sign = 1 
    for i in range(k, 0, -1): 
     pow_term = (i ** n) 
     comb_term = comb(k, i) 
     prod = pow_term * comb_term 
     prod = prod * sign 
     res = res + prod 
     sign = sign * -1 
    return res 

def p_exactly_k(n, k): 
    """ 
    Returns the probability of `B` containing exactly `k` unique elements 
    (also see notes above) 
    """ 

    return (comb(n, k) * k_numerator(n, k))/(n ** n) 

Answer 2

私はこの権利を理解している場合は100％を確認していません。しかし、のは、それを打破してみましょう：-loopは「selectionSize」を実行します つつrandomNodeListの大きさはO（n）の中にある

（nはノードの量である）、最良の場合と最悪の場合nは倍と。 単純なグラフでは、O（n-1）個の近傍を持つことができます。そう全体のループ（）ためN *（N-1の）はO（n^2）でなければならない

公理は正しいです。実際には、このアルゴリズムの上限を見つけることはできません。それは非決定論的です。あなたの乱数に依存します。あなたは（あなたが何度も何度も同じノードを選んで終わることができます）、おそらく無限ループを持っているので、交換して