c - 如何检查排序算法的大 O 表示法？

Question

我不知道如何解决它的复杂性等。如何知道它是否比其他排序算法更快？

我发现很难找到它，因为我的数学有点差。

#include <stdio.h>

int func(int arr[])
{
    int temp;
    int numofarrays=9999;
    for(int runtime=1; runtime<=numofarrays/2; runtime++)
    {
        for(int i=0; i<=numofarrays; i++)
        {
            if(arr[i] > arr[i+1])
            {
                temp=arr[i];
                arr[i]=arr[i+1];
                arr[i+1]=temp;
            }
            if(arr[numofarrays-i-1] > arr[numofarrays-i])
            {
                temp=arr[numofarrays-i-1];
                arr[numofarrays-i-1]=arr[numofarrays-i];
                arr[numofarrays-i]=temp;
            }
        }

    }
    for(int i=0; i<=9999; i++)
    {
        printf("%i\n",arr[i]);
    }
}
int main()
{
    int arr[10000];
    for(int i=0; i<=9999; i++)
    {
        arr[i]=rand() % 10;
    }

    func(arr);
}

标签： calgorithmsortingtime-complexitybig-o

Answer 1

大 o 符号是您编写的代码的步数限制到无穷大的地方。由于极限趋于无穷大，我们忽略系数并查看最大值。

for(int runtime=1; runtime<=numofarrays/2; runtime++)
{
    for(int i=0; i<=numofarrays; i++)
    {

这里，第一个循环的最大项是n，第二个循环的最大项是n。但是由于循环 2 为第一个循环的每一圈转 n 圈，所以我们将 n 乘以 n。结果是 O(n^2)。