使用分类数组实现一组

这是一个数据结构问题，但也涉及到实现。一个集合通常使用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

使用分类数组实现一组

回答

相关问题