使用分類數組實現一組

這是一個數據結構問題，但也涉及到實現。一個集合通常使用BST實現，但是我的教授希望我們知道如何在只給定有限選項時實現某些數據結構。所以他希望我們能夠理解如何僅使用數組來創建一個集合。使用分類數組實現一組

使用標準（未排序）陣列我瞭解執行/複雜性......

void add(Student[] arr, Student findstu) 
{ 
    Student stu = new Student(); 
    int i=0; 
    boolean found = false; 
    while(stu!=NULL) 
    { 
     stu = arr[i++]; 
     if (stu==findstu) 
     { 
      found = true; 
     } 
    } 
    if (found==false) 
    { 
     arr[i+1] = findstu; 
    } 
}

添加/刪除/包含的盟友幾乎相同的代碼，都將有第while循環，它會讓他們O（n）。

但是，如果我們使用了一個排序數組，爲什麼會包含O（lgn）並添加/刪除O（n）？

來源

2015-12-14 ohbrobig

這段代碼無效（不會編譯），即使修復不理想 – Amit

@Amit你可以擴展你的意思嗎？這裏的想法是不要有最好的運行時間...只需實施一些給定的約束 – ohbrobig

'Student stu = new Student（）;'是語法錯誤，因爲'stu'不是指針。這是不理想的，因爲你分配和初始化對象，而不需要它 – Amit

搜索將是O(logN)，因爲由於數組已排序，因此可以應用二進制搜索，該搜索的複雜性爲O(logN)。

插入和擦除將O(N)複雜（即，線性的時間），因爲每次將試圖插入或排序後的數組中刪除的元素，你將不得不您的陣列的一個位置的元素轉變其爲O(N)線性時間複雜。

來源

2015-12-14 21:15:30 101010

使用分類數組實現一組

回答

相關問題