首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >这段代码的复杂度是多少?我要用什么符号呢?

问这段代码的复杂度是多少?我要用什么符号呢?
EN

Stack Overflow用户
提问于 2012-03-07 05:57:53
回答 1查看 254关注 0票数 0

当我确定像这样的Java代码的复杂性时,我是不是必须用Theta或大O表示法来表示呢?

代码语言:javascript
复制
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)比较运算是线性的吗?我认为加法运算也是在固定时间内运行的。代码的总复杂度是多少?

EN

回答 1

Stack Overflow用户

回答已采纳

发布于 2012-03-07 06:09:58

如果考虑数字并从小到大进行排序,则代码为O(n²)。

  • 如果您的输入是反向排序(从大到小),则代码将是

(N)。

  • 如果您的输入已经排序,则此代码将是Θ(n²)

代码只是Insertion sort的一个变体,它只是使用一个列表而不是一个数组。

考虑下面这个例子的复杂性:

数字是1、2、3、4、5,您希望从小到大进行排序。

  1. 在第一次迭代后,你的列表将由1组成。(这发生在o(1)中),并且你不会访问内部循环。
  2. 在第二次迭代中,你有一个包含{1}的列表,因为你要插入2,所以你将访问一次while循环,在它之后插入它。
  3. 第三次迭代列表是{1 2}你访问while循环两次,并在it.
  4. ...

之后插入3

最后,你会得到类似于:0,1,2,3,4time‘s的内循环。

现在您可以将1 2 3 4 5编写为(5(5+1))/2)。

现在你可以把O(n(n+1) /2+ n)写成O(n²)。

票数 1
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/9592581

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档