运行排序算法的时间

Question

我编写了一个函数来按从旧到新的顺序对时间戳 (hh:mm:ss) 进行排序。我想知道我的代码的大概最坏情况运行时间，但我不知道如何确定。

我粗略的猜测是 O(n-1)^2 因为嵌套 for loop。我说得对吗？

如果不是，那么有人可以用 Big O 符号确定我的代码的大约运行时间是多少？

public void sortTimeStamp(SortTime timestamps[])
{
    for(int i=0;i<timestamps.length-1;i++)
    {
        for(int j=0;j<timestamps.length-1;j++)
        {
            if(timestamps[j].hour > timestamps[j+1].hour)
            {
                swap_timestamps(timestamps, j);
            }
            else
            if(timestamps[j].hour == timestamps[j+1].hour)
            {
                if(timestamps[j].minutes > timestamps[j+1].minutes)
                {
                     swap_timestamps(timestamps, j);
                }
                else
                if(timestamps[j].minutes == timestamps[j+1].minutes && timestamps[j].seconds > timestamps[j+1].seconds)
                {
                    swap_timestamps(timestamps, j);
                }

            }
        }
    }
}

交换函数

public void swap_timestamps(SortTime timestamps[], int index)
    {
        SortTime temp = timestamps[index];
        timestamps[index] = timestamps[index+1];
        timestamps[index+1] = temp;
    }

Answer 1

我觉得这个排序算法是O(n^2)。
你的答案是O((n-1)^2)，等于O(n^2-2n+1)。
但是大O符号O(f(n))表示"the time is approximately proportional for f(n)"（不完全正确，但很容易理解）
所以你不必考虑 -2n 或 1 术语。
你可以只考虑n^2项，不需要任何系数。

但是你可以做合并排序，时间复杂度是 O(n log n)
计数排序是可以的，因为hh:mm:ss只能表达86400种方式。它完成 O(n+k) 其中 k=86400.

运行排序算法的时间

Running time of sorting algorithm

java

algorithm

big-o