时间数组操作的复杂性 [英] Time complexity of Array Manipulation

问题描述

夫妇很基本的时间复杂度相关的问题在这里：

1. 什么是Java数组初始化的时间复杂度？例如，

    INT ARR [] =新的INT [5000]; 

   我猜测它是为O（n），或在不调用JVM一些疯狂的硬件巫术，它只需O（1）？




2. 有关插入或使用数组索引检索要素是什么？

   
   无效setNumber（整型数字，诠释arrIndex）{
     ARR [arrIndex] =号;
   }INT getNumber（INT arrIndex）{
     返回ARR [arrIndex]
   }
   

   我猜这是O（1）。但是说，如果arrIndex是4999的话，那不是指向数组的头指针计算出要检索的项目是在头+（INT大小）* arrIndex和'移动'N（〜5000）的位置检索从而使复杂度为O（n），而不是O（1）该项目。

   也许我们不考虑在硬件层面的东西，方便地调用它的时间复杂度的常量有关？可能有人请澄清？谢谢！

解决方案

您问过大约两件事，这通常是O（1）。前者比后者更复杂，所以我会以相反的顺序解决这些问题。

数组索引

回想一下，RAM代表随机存取存储器。这意味着（缓存效果除外）访问RAM的一部分将同样尽可能快地访问任何其他。这种感动的n你是指根本不会发生;柱塞电路被设计成使得无论设置的地址引脚将是在输出引脚上的下一个周期。

内存分配

这是一个事实，即有一个分配做了一堆幕后的工作复杂化。有丰富的在维基百科信息，但在一般（但丑陋的）感觉，这里的答案为O（1）除非事实并非如此。

即使阵列保证是零填充，你仍然可以看到O（1），因为很多平台上的地图内存，这已是零填充到过程。如果你真的很好奇，你可以看看的释放calloc （零填充分配）实施http://g.oswego.edu/dl/ HTML / malloc.html相对=nofollow> Doug Lea的malloc的。当然，undersand发生的事情低于，你需要另外一本书，或者冒险进入内核源。

Couple very basic time complexity related questions here:

1. What is the time complexity of array initialization in java? e.g.,

   int arr[] = new int[5000];

   I am guessing it to be O(n) or does the JVM invokes some crazy hardware voodoo magic that it takes only O(1)?

2. What about inserting or retrieving elements using array index?

   void setNumber(int number, int arrIndex) {
     arr[arrIndex] = number;
   }
   
   int getNumber(int arrIndex) {
     return arr[arrIndex];
   }
   

   I am guessing this to be O(1). But say if arrIndex is 4999 then, wouldn't the pointer that is pointing to the head of the array calculates that the item to be retrieved is at head+(size of int)*arrIndex and 'moves' n (~5000) position to retrieve that item thus making the complexity O(n) and not O(1).

   Perhaps we do not consider things at hardware level and conveniently call it the 'constant' associated with the time complexity? Could someone please clarify? Thanks!

解决方案

You've asked about two thing, which are usually O(1). The former is more complex than the latter, so I will address them in reverse order.

Array Indexing

Recall that 'RAM' stands for "Random Access Memory". This means that (cache effects aside) accessing one portion of ram will be equally as fast as accessing any other. This "moving" of n you refer to simply doesn't happen; the ram circuitry is designed such that whatever you set the address pins to will be on the output pins the next cycle.

Memory Allocation

This is complicated by the fact that there's an allocator doing a bunch of work behind the scenes. There's a wealth of information on Wikipedia, but in a general (but ugly) sense, the answer here is "O(1) except when it isn't."

Even if the array was guaranteed to be zero-filled, you could still see O(1), since many platforms map memory which has already been zero-filled into your process. If you're really curious you could look at the calloc(zero-filled allocation) implementation in Doug Lea's Malloc. Of course, to undersand what goes on below that, you'll need another book, or have to venture into the kernel source.

这篇关于时间数组操作的复杂性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！