0

好的，还在学习数组。我编写了这段代码，它用 0 到 1（不包含）之间的随机数填充名为“rand”的数组。我想开始学习复杂性。For循环执行n次（100次），每次都需要O（1）时间，所以最坏的情况是O（n），对吗？此外，我使用 ArrayList 来存储 100 个元素，并导入“Collections”并使用 Collections.sort() 方法对元素进行排序。

import java.util.Arrays;
    public class random
    {
        public static void main(String args[])
        {
            double[] rand=new double[10];

                    for(int i=0;i<rand.length;i++)
                    {
                        rand[i]=(double) Math.random();
                        System.out.println(rand[i]);
                    }   

                    Arrays.sort(rand);
                    System.out.println(Arrays.toString(rand));
        }
    }

数组列表：

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

public class random
{
    public static void main(String args[])
    {
        ArrayList<Double> MyArrayList=new ArrayList<Double>();


        for(int i=0;i<100;i++)
        {               
            MyArrayList.add(Math.random());
        }

        Collections.sort(MyArrayList);


        for(int j=0;j<MyArrayList.size();j++)
        {
            System.out.println(MyArrayList.get(j));
        }

    }
}
4

1 回答 1

2

是的，你是对的，添加 N 个项目的复杂度是 O(N)。根据文档，在大多数情况下，排序需要额外的 O(N * log(N)) ：

排序算法是一种调整过的快速排序，改编自 Jon L. Bentley 和 M. Douglas McIlroy 的“Engineering a Sort Function”，Software-Practice and Experience，Vol。23(11) P. 1249-1265（1993 年 11 月）。该算法在许多数据集上提供 n*log(n) 性能，导致其他快速排序降低到二次性能。

ArrayList仍然由数组支持，因此复杂性将是相同的，除非偶尔调整大小，否则无论如何都会摊销。

于 2012-09-01T15:48:46.673 回答