相关疑难解决方法(0)

我试图比较堆栈和队列操作的增长率(运行时和空间),当实现为数组和链接列表时.到目前为止,我只能找到队列pop()的平均案例运行时间,但没有全面探索这两个数据结构并比较它们的运行时/空间行为.

具体地讲,我想找比较push()和pop()用于两个队列和堆栈,作为实现两个阵列和链表(因此2次操作×2种结构×2个实施方式中,或8个值).

另外,我会欣赏这两者的最佳,平均和最差情况值,以及与它们消耗的空间量有关的任何事情.

我能找到的最接近的是"所有cs作弊表的母亲"pdf,这显然是高级算法和离散函数的主人或博士级备忘单.

我只是在寻找一种方法来确定何时何地应该使用基于数组的实现与基于列表的堆栈和队列实现.

在Java中声明大小为n的数组的运行时间是多少？我想这将取决于内存是否zero'ed出来的垃圾收集(在这种情况下,它可能是O(1)),或在初始化(在这种情况下,它不得不为O(N)).

事实上,这是几天前提出的一个面试问题.

面试官要我表达之间的区别ArrayList和LinkedList,并要求以优化插入操作ArrayList,换句话说,重新实现add(int index, E element),当然还有复杂get(int index)的操作都可以牺牲.

我的答案是将数组分成k个子数组并更新一个计数数组,表示相应子数组中已有的元素数.并且每个子数组的内存都以预期的初始大小动态分配.当我需要将数据插入时ArrayList,我可以先找到一个子数组,然后在一个小数组中进行操作.如果插入不是太频繁或索引是均匀分布的,插入的时间复杂度可以是O(log(k) + n/k + k)平均的,这log(k)意味着我们应该首先在计数数组的和数组上使用二进制搜索来定位子数组,n/k用于数据移动甚至是内存重新分配,k代表sum数组的更新.

我相信有更好的解决方案.我确实需要一些建议,谢谢!

这里我有一个指向第一个元素的指针和一个int来保存元素的数量.如何在内存分配中添加malloc和calloc？

struct vector_new           
  {
  char *start;
  int count;
  }