当我确定像这样的Java代码的复杂性时,我是不是必须用Theta或大O表示法来表示呢?
List<Person> sortedPersons = new ArrayList<Person>();
List<Person> people = new ArrayList<Person>();
for (int i = 0; i < people.size(); i++) {
Person toadd = people.get(i);
int index = 0;
while(index < sortedPersons.size() && sortedPersons.get(index).compareTo(toadd) < 0)
index++;
sortedPersons.add(index, toadd);
}我知道for循环是O(n) (或者是\Theta(n)?)get操作在固定时间内运行,因此O(1)。但是while循环呢?sortedPersons.size():O(1) sortedPersons.get():O(1)比较运算是线性的吗?我认为加法运算也是在固定时间内运行的。代码的总复杂度是多少?
发布于 2012-03-07 06:09:58
如果考虑数字并从小到大进行排序,则代码为O(n²)。
(N)。
代码只是Insertion sort的一个变体,它只是使用一个列表而不是一个数组。
考虑下面这个例子的复杂性:
数字是1、2、3、4、5,您希望从小到大进行排序。
之后插入3
最后,你会得到类似于:0,1,2,3,4time‘s的内循环。
现在您可以将1 2 3 4 5编写为(5(5+1))/2)。
现在你可以把O(n(n+1) /2+ n)写成O(n²)。
https://stackoverflow.com/questions/9592581
复制相似问题