java – 迭代数组列表的时间复杂度
我有一个数组列表,我迭代.在每次迭代中,我调用get()来获取一个元素,如果该项通过某些条件,则使用add()将其添加到新的数组列表中
List<Item> items = new ArrayList<Item>(); List<Item> lessItems = new ArrayList<Item>(); for(int index = 0; index < items.size(); index++){ Item toCheck = items.get(i); if(toCheck meets some condition){ lessItems.add(toCheck); } } 我不确定这里的时间复杂程度.我在所有项目上调用get(),这样就是O(n).然后我也在潜在的所有项目上调用add(),所以还有另一个O(n).这个不太确定. 解决方法
所有其他答案都错了.
>迭代项列表的第一个循环:复杂度为O(n) 因此,代码的复杂性为:O(n)*摊销O(1).简而言之就是O(n) 另一个参考: dynamic array 附加说明1: 如果在阵列末尾插入的复杂度是O(N),那么总复杂度是O(N ^ 2),而不是其他答案所说的O(2 * N).因为插入的总复杂度将是:1 2 3 … n = n *(n 1)/ 2 附加说明2: 如official document所述:
附加说明3: 这是我从官方java源代码中获取的grow方法的逻辑: private void ensureExplicitCapacity(int minCapacity) { modCount++; // overflow-conscious code if (minCapacity - elementData.length > 0) grow(minCapacity); } private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // minCapacity is usually close to size,so this is a win: elementData = Arrays.copyOf(elementData,newCapacity); } 正如源代码所说,当程序添加使数组大小大于当前容量的元素时,Array将会增长.增长阵列的新大小将是: int newCapacity = oldCapacity + (oldCapacity >> 1); 这是一个使插入分摊的技巧O(1) (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |