時間計算量の実測値と理論値が大きく異なる理由

Question

時間計算量（処理にかかる時間）を実際にテストしてみたくて以下のコードを書きました。
内容はシンプルです。

0～ｎの整数を1ずつ加算してコンソールにn行表示させる処理を、Stopwatchクラスで経過時間を求めてms単位で結果を出力させます。
コードにはn=10000と書きましたが、ｎに様々な値を代入して何度か実行して平均的な経過時間を求めました。
for文によりn回のConsole.WriteLine()を実行するので、経過時間はｎに依存すると考えました。
つまりｎを2倍にすれば経過時間も2倍近くになるだろうという予想です。
しかし予想は外れました。

n=10,000の時の経過時間は6732ms(倍率1.00）
n=20,000の時の経過時間は8305ms(倍率1.23)
n=100,000の時の経過時間は19490ms(倍率2.89)

ｎを2倍、10倍と増やしても経過時間は比例しませんでした。
これは一体なぜでしょうか。

using System;
using System.Diagnostics;

namespace SortTest
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = 10000;
            Stopwatch stopWatch = new Stopwatch();
            stopWatch.Start();
            // timer start
            for (int i = 0; i < n; i++)
                Console.WriteLine(i);
            // timer stop
            stopWatch.Stop();
            TimeSpan ts = stopWatch.Elapsed;
            Console.WriteLine($"経過時間：{ts.Seconds * 1000 + ts.Milliseconds}m秒");
        }
    }
}

Comments

[KOZ6.0]

・Console.WriteLine(i); ではなく、Console.WriteLine(i.ToString("00000000")); として桁数をそろえてみましょう
・デバッグ実行すると、デバッガの影響を受けるので、コマンドプロンプトから実行してみましょう。
・その際、引数で回数を指定できるようにしておくといいですね。
・ばらつきが出るので、複数回試行して平均を求めてみましょう。

[Zuishin]

> Console.WriteLine

これを使っているからです。
誤差が大きくなるので、計算時間を計る時には出力は必ずループの外に出すのが鉄則です。

[unigorou]

アドバイスありがとうございます。
昨日の質問ではVisual Studio2019の「デバッグ無しで実行」で得られた結果を載せました。
ご指摘の通り、Console.WriteLine(i)の箇所に変更を加え、コマンドプロンプト上で実行しました。
結果は以下の通りです。いずれも何度か実行した結果の平均値です。

n=10000の時、経過時間は980ms(倍率1.00)
n=20000の時、経過時間は1877ms(倍率1.91)
n=100000の時、経過時間は9193ms(倍率9.38)

今回の結果は前回とは対照的にnに比例した数値となりました。
新たな疑問点として、
①コマンドプロンプトの実行と「デバッグ無しで実行」では両者共にデバッガが走らないと思いますが、こういった実行速度の差ができるのは何か他に要因があるのでしょうか。
②Console.WriteLine(i) → Console.WriteLine(i.ToString("00000000"))の修正前後において、コマンドプロンプト上で実行した結果、経過時間が異なりました。Console.WriteLine(i)の方が経過時間が長く(n=10000の時、経過時間は1353ms)、実行速度に差が出る上に桁数の大きいほうが速いということが意外だったのですが、こちらもなぜそうなるのか検討がつかず、可能であればご助言頂けると幸いです。

[Zuishin]

だから言ってるじゃないか。コンソールバッファについて調べてきたらいい。

[KOZ6.0]

① よくわからんですね。まぁ実行時間に影響しているのは確かでしょう。
② 実装を見るとわかるかも。
Console.WriteLine(int)
https://referencesource.microsoft.com/#mscorlib/system/console.cs,82d5745bf4a5ecc6
Console.WriteLine(string)
https://referencesource.microsoft.com/#mscorlib/system/console.cs,5ac7c4fda643413b

[unigorou]

アドバイスありがとうございます。
調べてみます。