c++ - コードの効率

Question

2次元配列の各行の合計を求める際の効率 (big O表記) を見つける方法

void findTotal(int arr[3][],int rows,int cols)
{ 
    int *total=new int[rows];
    int sum;
    for(int r=0;r<rows;r++)
    {
        sum=0;
        for(int c=0;c<cols;c++)
            sum=sum+arr[r][c];
        total[r]=sum;
    }
    for(int k=0;k<rows;k++)
        cout<<total[k]<<endl;
    delete []total;
}

Answer 1

SOへようこそ！

この説明で少しは理解できると思います。

効率は基本的に次のように定義できます。

「入力サイズ n に関する関数の成長」。

Big O 表記法を使用すると、アルゴリズムが入力サイズの変化に (時間またはスペース要件の観点から) どのように応答するかによってアルゴリズムを分類できます。

あなたの場合、入力は2D配列で、行数と列数があります。ループforはすべての行を通過し、ネストされたループは 2D 配列のすべての行のすべての列を通過します。H2CO3のとおりです。この関数の Big O はO(rows*columns)

さまざまな効率の他の例は次のとおりです。

O(n) - 線形 - 入力サイズと同じ速度で成長します。例 - ソートされていない配列内のアイテムを見つける

O(1) - 定数 - 成長しない - 変わらない。例 - ハッシュ テーブル。

O(log n) - 対数; 例: 二分探索

O(n log n) - 線形; 例: マージソート、クイックソートなど

詳細については、常に質問を Google で検索する必要があります。

ウィキペディアには、 Big O Notationなどのコンピューター サイエンスに関する優れた記事のリストもあります。