包含预定义方法的java计算算法的复杂性

Question

拥有以下简单的Java代码：

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Simple {
    public static void main(String[] args) {
        List list = new ArrayList();
        list.add(5);
        list.add(4);
        list.add(3);
        Collections.sort(list);
    }
} 

1. 在不知道集合的复杂性的情况下，如何计算该算法的复杂性。排序方法

2. 我应该去java文档搜索收藏吗。对源代码进行排序，然后计算其复杂性

注：收藏。sort只是预定义方法的一个例子

谢谢

Answer 1

例如，这个hello world程序有一个恒定的时间复杂度，因为没有输入。 在打印字符串时，实际上并没有进行任何计算

Answer 2

How can i calculate this algorithm's complexity without knowing the complexity of System.out.println method ?

严格地说，你不能

另一方面，在算法分析中包含详细的I/O复杂性是不正常的。通常，我们假设I/O的行为方式与人们通常理解的行为方式相同。。。因为真正的复杂性分析很难进行

实际上，假设简单I/O（像这样）的复杂性为O(N)，其中N是读取或写入的字节/字符数

Am i supposed to go to the java doc and search for System.out.println source code and then calculate its complexity ?

不，见上图

---

Ok understood , but what if i call the sort predefined java method ?

{}的javadoc说：

This implementation defers to the List.sort(Comparator) method using the specified list and a null comparator.

反过来说：

Implementation note: This implementation is a stable, adaptive, iterative mergesort that requires far fewer than n lg(n) comparisons when the input array is partially sorted, while offering the performance of a traditional mergesort when the input array is randomly ordered. If the input array is nearly sorted, the implementation requires approximately n comparisons. Temporary storage requirements vary from a small constant for nearly sorted input arrays to n/2 object references for randomly ordered input arrays.

---

一般来说，要确定标准类库中类的复杂性，请阅读javadoc，如果javadoc没有说明，请查找并分析源代码。。。或者根据您对实际使用的数据结构的了解做出合理的假设

环境应该决定你的复杂性分析是否需要严格。如果不需要严谨，你可以在分析中走捷径。。。如果你得到了正确的答案：-）

在这两种情况下，请注意，算法几乎总是“一个实现细节”，性能和空间复杂性（至少在理论上）可能会发生变化

Answer 3

样本没有任何输入，所以O是一个常数，或O（1）。例如，只有当您有一个大小为N的输入，并且在程序中有某种循环或对相关函数的递归调用时，复杂性才有意义，因此运行时间取决于输入。正如Sanjeev Sharma指出的，在这种情况下，寻找复杂性是荒谬的