如何找到以下新的快速排序算法的精确时间复杂度和空间复杂度

Question

我已经创建了新的排序算法,这个算法的基本概念是从给定列表中找到最小和最大的元素,并用左角和右角元素交换它们,这将重复直到我们到达mid元素.

该算法在比Quick sort和merge sort更短的时间内执行.我想确定这个算法是否比快速排序更好.

我的算法代码

public class VeryQuickVersion1 
{

    public static void main(String args[]) 
    {

        long current = System.nanoTime();

        int[] first = { 8 ,1 ,3 ,2, 6, 5, 7, 4, 12 ,9, 11 ,10 ,14 ,13, 15};

        for (int x=0,y=first.length - 1;x<y;x++,y--) 
        {
            int low = 0;
            int high = 0;
            int li = 0;
            int hi = 0;
            for (int i = x; i <= y; i++) 
            {
                if (i == x)
                {
                    low = first[i];
                    high = first[i];
                }
                if (low > first[i]) 
                {
                    low = first[i];
                    li = i;
                }
                if (high < first[i])
                {
                    high = first[i];
                    hi = i;
                }
            }

            first[li]=first[x];
            first[hi]=first[y];

            first[x]=low;
            first[y]=high;
        }
    /*  for(int i:first){
            System.out.println(i);
        }*/
        System.out.println(System.nanoTime() - current);
     }
}

该算法所花费的时间是:10148并且快速排序算法对于相同列表所花费的时间是:17498

Answer 1

上述算法的时间复杂度似乎是O(n^2).

如您所见,有2个嵌套for循环.外部一个从运行x = 0, y = n到x < y,并且在每个步骤它减少x++和y--.而其他内部回路从x到y.

这可以看作是一个系列n + (n-2) + (n-4) + .... + 0.这显然给了时间复杂性O(n^2)

时间复杂度不是按照您的方式计算的.您应该检查当输入的大小增加时,此程序所花费的时间将如何增加.并使用不同类型的输入(ex exnding,random等)测试相同的内容.

在收集了大量输入和不同类型输入的数据之后,您将看到作为O(nlogn)时间复杂度的算法与具有O(n^2)时间复杂度的算法之间的差异.

注意:您可以看到本网站如何增加时间的真正差异.注意在输入长度增加到的时间后,时间会增加50000.