时间戳

首页 > 解决方案 > 如何在 C 中分析算法的运行时间？

c - 如何在 C 中分析算法的运行时间？

问题描述

我应该编写一个算法并分析和比较它在最佳和最坏情况下的运行时间。作业长这样

选择一种算法并在 C 中实现它。然后至少在运行时间、内存需求等标准中对其进行分析。这种分析必须在您的代码中可视化，并使用您从代码中自动获取的数据。例如，如果您要分析代码的运行时间，您应该编辑代码以迭代处理不同大小的数据，并在每次运行时用简单的条形图显示其运行时间。

我对这个东西很陌生，所以我不知道怎么做。IDE 中是否有可使用的功能或内置工具？

这是我的代码。这是一个简单的砖排序算法。

#include <stdio.h>

int n, i, a[100], temp, isSorted;

int brickSort(int a[], int n)
{
    isSorted=0;
    
    while(isSorted==0)
    {
        isSorted=1;
        
        for(i=0; i<=n-2; i=i+2)
        {
            if(a[i]>a[i+1])
            {
                temp=a[i];
                a[i]=a[i+1];
                a[i+1]=temp;
                isSorted=0;
            }
        }
        
        for(i=1; i<=n-2; i=i+2)
        {
            if(a[i]>a[i+1])
            {
                temp=a[i];
                a[i]=a[i+1];
                a[i+1]=temp;
                isSorted=0;
            }
        }
    }
    
    for(i=0; i<n; i++)
    {
        printf("%d ", a[i]);
    }
}

int main()
{
    printf("Enter the amount of numbers ");
    scanf("%d", &n);
    
    for(i=0; i<n; i++)
    {
        printf("Enter number ");
        scanf("%d", &a[i]);
    }
    
    return brickSort(a, n);

    return 0;
}

标签： c

解决方案

如何在 C 中分析算法的运行时间？

我不知道你是怎么做到的。

我的做法是尝试估计潜在缓存未命中的总数和潜在分支错误预测的总数。理论是现代 CPU 每个周期可以执行多条指令，但是缓存未命中或分支错误预测会花费数十或数百个周期，因此大多数正常指令的成本通常可以忽略/可忽略，并且只有缓存未命中和分支错误预测有足够大的性能影响来担心。

对于您的代码；对于分支错误预测；在外循环的第一次迭代之后，分支很可能if(a[i]>a[i+1])会很快被 CPU 的分支预测器“预测为未采用” 。while(isSorted==0)可以合理地说（作为“不准确但足够接近”的估计），分支错误预测的数量将取决于原始数组的排序方式（例如数组“1、3、7、12、14”已经已排序并且不会有很多分支错误预测，但是“14、12、7、3、1”非常未排序并且会导致更多的分支错误预测）。分支本身可以被忽略（可能错误预测一次，这while(isSorted==0)不足以担心）。

对于缓存未命中，有两种情况 - 整个数组都适合缓存（并且潜在的缓存未命中总数与数组的大小直接相关）；或者数组太大而无法放入缓存中，因此它会不断地将日光从缓存中剔除（并且潜在的缓存未命中总数与数组的大小乘以while(isSorted==0)外部循环执行的次数有关）。外循环执行的次数while(isSorted==0)取决于原始数组的排序程度。

然而...

你的问题可能不是你想问的问题；你可能想问“我的大学/课程如何让我分析算法的运行时间？”。如果您的大学/课程最近向您介绍了“大 O 符号”（请参阅​​ https://en.wikipedia.org/wiki/Big_O_notation），那么您的大学/课程很可能希望您使用“大 O 符号”来查找一个毫无意义的伪估计，与性能几乎没有相关性（在“对于 n 的所有实际值而言，O(n*n) 比 O(n) 快”方式）。

推荐阅读