アルゴリズムの問題を解決しようとしていますが、時間の制約内で解決するには、作成に線形または線形よりも時間がかかる累積度数表を実装する必要がありますか? 私の入力は整数のみです。したがって、頻度表のキーは整数のみです。私が思いついた簡単な実装は次のとおりです (次のコードでは、cumulative_freq_table がハッシュマップであると仮定します)。
read x
for key in range(x, N):
if key in cumulative_freq_table:
cumulative_freq_table[key] += 1
アルゴリズム関連のコースを勉強したことはありませんが、その複雑さは O(N^2) 程度だと思います。これは O(N^2) よりも時間内に実行できますか?