尽管复杂性相同

Question

我有任务比较3D矩阵气泡排序和插入排序执行时间。他们只能在每一行中排序数字。我在Java中写了一个方法，如下所示：

static void BubbleSort(char tab2D[][], int tabSize) throws InterruptedException {
    for (int i = 0; i < tabSize; i++) {
        for (int j = 1; j < tabSize - i; j++) {
            for (int k = 0; k < tabSize; k++) {
                if (tab2D[k][j - 1] > tab2D[k][j]) {
                    char temp = tab2D[k][j];
                    tab2D[k][j] = tab2D[k][j - 1];
                    tab2D[k][j - 1] = temp;
                }
            }
        }
    }
}
    

static void InsertionSort(char tab2D[][], int size) throws InterruptedException {
    char temp;
    int i, j;
    
    for (int ii = 0; ii < size; ii++) {
        for (i = 1; i < size; i++) {
            temp = tab2D[ii][i];
            for (j = i - 1; j >= 0 && tab2D[ii][j] > temp; j--) {
                tab2D[ii][j + 1] = tab2D[ii][j];
            }
            tab2D[ii][j + 1] = temp;
        }
    }
}

据我所知，这两种算法都具有时间复杂性o（n^2），但是我对这两种算法都有我的结果：

100x100 Matrix: Bubble sort=21 ms, Insertion sort=3 ms
300x300 Matrix: Bubble sort=495 ms, Insertion sort=20 ms
700x700 Matrix: Bubble sort=6877 ms, Insertion sort=249 ms

测量时间：

start = System.currentTimeMillis();
// sort method
stop = System.currentTimeMillis();
time = stop - start;

我不太了解问题，因为泡泡排序与插入相比太慢。据我了解，他们的时间应该相似。甚至检查了两个版本的算法编辑它们仅排序数组，气泡排序仍然慢得多，我无法说明原因。 我尝试尝试的下一件事是将螺纹放置。这样做之后，我意识到时代最终看起来相似，只有一些不同。有人可以解释为什么会发生这种情况吗？我在正确之前测量了时间吗？

Answer 1

如评论中提到的那样，人们不能根据给定时间的复杂性对运行算法所需的实际时间说任何有用的话。具有相同时间复杂性的两种算法不一定需要相同的时间才能完成同一工作。

话虽如此，这是两个函数之间的一些差异，这些函数解释了为什么insertionsort平均需要更少的时间来完成这项工作：

• 如果我们忽略了tab2d [ii] [j] ＆gt; temp条件insertionsort的内部循环中，两个功能都执行相同的循环迭代次数。但是，由于insertionsort在内部循环中具有可以使其早期退出的条件，因此insertionsort通常会进行更少的迭代。

• 两者都在其内部循环中进行数据比较，但是bubblesort必须从数组中读取两个值才能做到这一点，而in insertionsort仅需要一个对数组的访问（因为另一个值在temp中）

  


• insertionsort的内环可以集中在一个气泡中的一个值上，这意味着它没有实际上必须进行交换，但仅 copy 。 Bubblesort必须交换，涉及三个分配而不是一个。当然，bubblesort不必在其内部循环的每个迭代中交换，但这与insertionsort不移动<的事实相反。 em> All 数组值（在循环范围内） - 因为它具有早期出口。这给人一种bubblesort进行3个作业的感觉，其中insertionsort只需要1个分配（加上内部循环外2个分配的开销）。我们可以看到，bubblesort将执行比insertionsort。

  执行更多的作业（涉及数组）。