処理時間（計算量）はデータ量に比例するとは限りません。
例えば、データ量が10倍になったからと言って、処理時間も10倍になるとは限りません。
処理時間が何倍になるかは、アルゴリズムにより決まります。
アルゴリズム次第では、データ量が10倍になった時に処理時間が100倍になることも有り得ます。
今回は、試しに、Java作成したソート処理の実行時間を測ってみます。
アルゴリズムはバブルソートです。
----
【サンプルコード】
・BubbleSort.java
import java.util.ArrayList;
import java.util.Collections;
public class BubbleSort {
public static void main(String[] args) {
// データ量（どちらかの行をコメントアウト）
int num = 10000;
// int num = 100000;
// ソート対象の配列
ArrayList<Integer> array = new ArrayList<>();
for (int i = 0; i < num; i++) {
array.add(i);
}
Collections.shuffle(array);
// 回答の配列
ArrayList<Integer> answer = new ArrayList<>();
for (int i = 0; i < num; i++) {
answer.add(i);
}
// ソート処理実行
long startTime = System.currentTimeMillis();
sort(array);
long endTime = System.currentTimeMillis();
// 回答通りか確認
int diffCount = 0;
for (int i = 0; i < num; i++) {
if (array.get(i).intValue() != answer.get(i).intValue()) {
System.out.println( (i + 1) + "つ目の要素の内容を出力");
System.out.println(" 結果：" + array.get(i));
System.out.println(" 回答：" + answer.get(i));
diffCount++;
}
}
if (diffCount == 0) {
System.out.println("差異無し。");
}
// 秒数出力
System.out.println( (endTime - startTime) + " ミリ秒");
}
static void sort(ArrayList<Integer> array) {
// 左から順番に値を確定させていく
// 添字の最小は0、最大はarray.size() - 1
for (int i = 0; i < array.size() - 1; i++) {
// 走査は右から
for (int j = array.size() - 1; j > i; j--) {
// 入れ替え処理（左が右より大きければ入れ替え）
if (array.get(j - 1) > array.get(j)) {
int tmp = array.get(j - 1);
array.set(j - 1, array.get(j));
array.set(j, tmp);
}
}
}
}
}
【実行時間】
・データ量が10000レコードの場合
１回目：1272ミリ秒
２回目：2826ミリ秒
３回目：1075ミリ秒
・データ量が100000レコードの場合
１回目：335986ミリ秒
２回目：305728ミリ秒
３回目：289040ミリ秒
----
以上のように、データ量が10倍になった場合に、実行時間も100倍（実測ではそれ以上）になりました。
なぜ実行時間がデータ量に比例しないのかと言うと、このアルゴリズムでは二重ループが発生するからです。
二重ループの中の処理が行われる回数は、10000レコードの場合は「1万 * 1万」（正確には「1万 * 9999」）回ですが、100000レコードの場合は「10万 * 10万」（正確には「10万 * 99999」）回となり、100倍の差となります。
この差が、実行時間にも反映されます。
専門用語で言うと、このような概念は「O(オーダ)」と呼ばれます。
（詳しくは、以前の記事（
https://cyzennt.co.jp/blog/2019/08/17/o%e3%82%aa%e3%83%bc%e3%83%80%e3%81%ae%e6%a6%82%e5%bf%b5%e3%81%a8%e5%ae%9f%e5%8b%99%e3%81%a7%e3%81%ae%e4%bd%bf%e3%81%84%e9%81%93/）で紹介しています）
実務でも、大量のデータを処理する必要がある場合は、「O(オーダ)」の概念や、最適なアルゴリズムを意識する必要があります。
競技プログラミングでは最適なアルゴリズムを考えさせる問題が頻出なので、詳しく学びたい方は手を出してみると面白いと思います。
