英文:
In an ArrayList if an element is removed at index 0 using remove(), then what will be the time complexity?
问题
我认为时间复杂度将为O(1)。因为在remove方法的声明中没有循环。如果我对时间复杂性的思考方法是错误的，请告诉我。
remove()方法的声明：
public synchronized E remove(int index)
{
modCount++;
if (index >= elementCount)
throw new ArrayIndexOutOfBoundsException(index);
E oldValue = elementData(index);
int numMoved = elementCount - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--elementCount] = null; // 让垃圾回收进行处理
return oldValue;
}
英文:
I think that the time complexity will be O(1). Since there are no loops in the declaration of remove method. Please let me know if my approach to think about time complexity is incorrect.
Declaration of remove():
public synchronized E remove(int index)
{
modCount++;
if (index >= elementCount)
throw new ArrayIndexOutOfBoundsException(index);
E oldValue = elementData(index);
int numMoved = elementCount - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--elementCount] = null; // Let gc do its work
return oldValue;
}
答案1
得分: 1
这是不正确的。尽管你看不到单词“for”或“while”，但在那里有一个循环。 （提示：该函数内部调用的所有函数的时间复杂性是多少？）
英文:
This is incorrect. There's a loop there, even if you don't see the word "for" or "while." (Hint: what are the time complexities of all the functions called inside that function?)
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论