计算for循环的近似运行时间

Question

我的C#Windows窗体应用程序中有一段代码如下所示:

List<string> RESULT_LIST = new List<string>();
int[] arr = My_LIST.ToArray();

string s = "";

Stopwatch sw = new Stopwatch();
sw.Start();

for (int i = 0; i < arr.Length; i++)
{
  int counter = i;
  for (int j = 1; j <= arr.Length; j++)
  {
    counter++;
    if (counter == arr.Length)
    {
      counter = 0;
    }
    s += arr[counter].ToString();
    RESULT_LIST.Add(s);
  }
  s = "";
}
sw.Stop();
TimeSpan ts = sw.Elapsed;
string elapsedTime = String.Format("{0:00}", ts.TotalMilliseconds * 1000);
MessageBox.Show(elapsedTime);

我使用此代码获取我的列表的数字的任意组合.我表现得像My_LIST一样递归.下图非常清楚地表明了我的目的:

我需要做的就是:

制定公式来计算这两个嵌套for循环的近似运行时间,以猜测任何长度的运行时间,并帮助用户知道他/她必须等待的大致时间.

我使用过这样的C#秒表:Stopwatch sw = new Stopwatch();显示运行时间,下面是结果(请注意,为了减少出错的可能性,我为每个长度重复计算三次,数字显示以纳秒为单位的时间分别为第一次,第二次和第三次尝试.):

1. arr.Length = 400; 127838 - 107251 - 100898
2. arr.Length = 800; 751282 - 750574 - 739869
3. arr.Length = 1200; 2320517 - 2136107 - 2146099
4. arr.Length = 2000; 8502631 - 7554743 - 7635173

请注意,My_LIST 中只有一位数字可以使列表中添加数字的时间大致相等.

我怎样才能找出arr.Length和运行时间之间的关系？

Answer 1

首先,我们假设您已经检查了算法,并注意到它在数组长度上似乎是二次的.这告诉我们,运行所需的时间应该是形式的函数

t = A + B n + C n ²

您通过多次运行代码并使用不同的n值和测量t来收集一些观察结果.这是一个很好的方法.

现在的问题是:A,B和C的最佳值是什么,它们与您的观察结果密切匹配？

这个问题可以通过各种方式解决; 我建议您使用最小二乘回归方法来开始,看看您是否获得了良好的结果.这里有一个页面:

www.efunda.com/math/leastsquares/lstsqr2dcurve.cfm

更新:我再次看了你的算法并意识到它是立方的,因为你在内循环中有一个二次字符串连接.所以这种技术可能效果不好.我建议你使用StringBuilder你的算法二次方.

现在,假设您事先并不知道问题是二次方的.那你如何确定公式呢？一个好的开始是在日志规模纸上绘制你的点数; 如果它们大致形成一条直线,则该线的斜率为您提供关于多项式幂的线索.如果他们没有形成直线 - 那么,当你来到它时,穿过那座桥.