我编写了一个算法来查找链表中的重复项。
对于每个节点，我从列表的头部迭代到当前节点，如果它是重复的，则将其删除。
我的算法的复杂度是多少？
问问题
87 次
1 回答
4
算法的复杂性是Θ(n^2) 最坏的情况，因为如果没有重复，你会为每个节点迭代线性增加的次数，导致1 + 2 + .... + n总读取数为Θ(n^2)（来自算术级数的总和）
在最好的情况下，复杂性是Θ(n)- 如果所有元素都是Θ(n)重复的Θ(n)
于 2012-12-17T10:33:34.967 回答