1

我和我的搭档正在尝试编写 LinkedList 数据结构。我们已经完成了数据结构，并且它可以使用所有必需的方法正常运行。我们需要对 LinkedList 类中的 addFirst() 方法与 Java ArrayList 结构的 add(0, item) 方法的运行时进行比较测试。我们的 LinkedList 数据结构的 addFirst() 方法的预期复杂度是 O(1) 常数。这在我们的测试中成立。在 ArrayList add() 方法的计时中，我们预计复杂度为 O(N)，但我们再次收到大约 O(1) 常数的复杂度。这似乎是一个奇怪的差异，因为我们使用的是 Java 的 ArrayList。我们认为我们的时间结构可能存在问题，如果有人能帮助我们确定我们的问题，我们将不胜感激。

public class timingAnalysis {

public static void main(String[] args) {

    //timeAddFirst();
    timeAddArray();

}

public static void timeAddFirst()
{
    long startTime, midTime, endTime;
    long timesToLoop = 10000;
    int inputSize = 20000;

    MyLinkedList<Long> linkedList = new MyLinkedList<Long>();

    for (; inputSize <= 1000000; inputSize = inputSize + 20000)
    {
        // Clear the collection so we can add new random
        // values.
        linkedList.clear();

        // Let some time pass to stabilize the thread.
        startTime = System.nanoTime();

        while (System.nanoTime() - startTime < 1000000000)
        {   }

        // Start timing.
        startTime = System.nanoTime();

        for (long i = 0; i < timesToLoop; i++)
            linkedList.addFirst(i);

        midTime = System.nanoTime();

        // Run an empty loop to capture the cost of running the loop.
        for (long i = 0; i < timesToLoop; i++) 
        {} // empty block

        endTime = System.nanoTime();

        // Compute the time, subtract the cost of running the loop from 
        // the cost of running the loop and computing the removeAll method.
        // Average it over the number of runs.
        double averageTime = ((midTime - startTime) - (endTime - midTime)) / timesToLoop;

        System.out.println(inputSize + " " + averageTime);
    }

}

public static void timeAddArray()
{
    long startTime, midTime, endTime;
    long timesToLoop = 10000;
    int inputSize = 20000;

    ArrayList<Long> testList = new ArrayList<Long>();

    for (; inputSize <= 1000000; inputSize = inputSize + 20000)
    {
        // Clear the collection so we can add new random
        // values.
        testList.clear();

        // Let some time pass to stabilize the thread.
        startTime = System.nanoTime();

        while (System.nanoTime() - startTime < 1000000000)
        {   }

        // Start timing.
        startTime = System.nanoTime();

        for (long i = 0; i < timesToLoop; i++)
            testList.add(0, i);

        midTime = System.nanoTime();

        // Run an empty loop to capture the cost of running the loop.
        for (long i = 0; i < timesToLoop; i++) 
        {} // empty block

        endTime = System.nanoTime();

        // Compute the time, subtract the cost of running the loop from 
        // the cost of running the loop and computing the removeAll method.
        // Average it over the number of runs.
        double averageTime = ((midTime - startTime) - (endTime - midTime)) / timesToLoop;

        System.out.println(inputSize + " " + averageTime);
    }

}

}

4

2 回答 2

2

您想测试不同的inputSize，但您执行操作以测试timesToLoop时间，这是恒定的。所以当然，这需要同样的时间。你应该使用：

for (long i = 0; i < inputSize; i++)
    testList.add(0, i);
于 2013-06-20T01:21:01.060 回答
-1

据我所知，Arraylist add 操作在 O(1) 时间内运行，因此您的实验结果是正确的。我认为arrayList add 方法的恒定时间是摊销的恒定时间。

根据 java doc：添加 n 个元素需要 O(N) 时间，这就是为什么添加摊销常数时间的原因。

于 2013-06-20T01:18:05.913 回答