これはばかげた質問かもしれませんが、アルゴリズムが 5 秒で 100,000 個の整数をソートするとします。同じアルゴリズムで 100,000 個の文字列も 5 秒で並べ替えられますか、それとも並べ替え時間が異なりますか?
5 に答える
2
文字列の比較は、整数の比較よりもコストがかかります。整数比較は、通常 CPU で発生する操作です。一方、文字列の比較はソフトウェアで実装する必要があります。したがって、文字列の比較には、文字列内の文字と同じ数の操作が必要になる場合があります。
--dmg
于 2013-05-18T02:43:57.183 に答える
1
Q: アルゴリズムは整数と文字列を同じ時間整合性で並べ替えますか?
A: "asymptotic"/"Big O notation"を意味する場合: はい。文字列は明らかに時間がかかりますが、それに比例して長くなります。
于 2013-05-18T02:56:20.997 に答える
0
簡単な答えはノーです。通常、文字列の並べ替えは、整数の並べ替えよりもはるかに時間がかかります。
"paper" と "papa" を並べ替えることを検討してください。最初の 4 文字を比較して、"paper" が "papa" より大きいことを確認する必要があります。これは、大きな文字列、特にフレーズではさらに長くなる可能性があります。
対照的に、整数の比較には 1 つの命令が必要です。
並べ替えを行うには、この種の比較を繰り返し行う必要があります。そのため、ほとんどの場合、文字列の並べ替えにはさらに時間がかかります。
于 2013-05-18T02:49:27.130 に答える
0
文字列にはさらに時間がかかります。整数は一連のビット演算として比較されます。文字列になると、整数に必要な各バイトまたは文字が同等の演算で比較されます。
実際には、一連の文字列を並べ替えるには、最悪の場合、すべての文字列の合計文字数を比較する必要があります。最悪のケースは、すべての文字列が同じであることです。すべての文字列が最後までトラバースされ、等しいことを確認する必要があります (strcmp() はこのように比較します)。
于 2013-05-18T02:50:13.680 に答える