第七章日常コードにおけるbigo

*サムネイルはThumbnail-Maker by oneookです.
第七章日常コードにおけるbigo
7.1偶数の平均値

double averageOfEvenNumbers(int* arr, int size)
{
    double sum = 0.0;
    int countOfEvenNumbers = 0;

    for (int i = 0; i < size; i++)
    {
        if (arr[i] % 2 == 0)
        {
            sum += arr[i];
            countOfEvenNumbers += 1;
        }
    }

    return sum / countOfEvenNumbers;
}

整数配列のすべての偶数の平均値を計算するアルゴリズム

データ要素Nはメソッド伝達の配列数

である.

偶数日は1)偶数,2)sum増加,3)countOfEvennumers増加−第3期

奇数が1)偶数確認->第1期

for文のほか,1)sum初期化,2)countOfEvennumbers初期化,3)sum/countOfEvennumbers計算->3段階

の最悪のシナリオ(すべての偶数)では、3 N+3フェーズ->O(N)

7.2単語ジェネレータ

void wordBuilder(char* arr, int size, string* result)
{
    int index = 0;

    for (int i = 0; i < size; i++)
    {
        for (int j = 0; j < size; j++)
        {
            if (i != j)
            {
                result[index++].append(1, arr[i]).append(1, arr[j]);
            }
        }
    }
}

文字配列におけるすべての二文字文字文字列の組合せを集約するアルゴリズム.

ネストリングアレイのデータ要素N*Nフェーズ->O(N)²)

の3文字の組み合わせ、for文が3回重なる->O(N)³)

7.3シナリオ例

int* sample(int* arr, int size)
{
    int* result = new int[3];

    result[0] = arr[0];
    result[1] = arr[size / 2];
    result[2] = arr[size - 1];

    return result;
}

アレイの前、中、後の値をサンプリングするアルゴリズム

Nは配列中の要素数

である.

Nでも

Nでも、常に第3ステップ(前、中、後の値を格納)->O(1)

を実行する.
7.4平均摂氏度を求める

double averageCelsius(double* fahrenheitReadings, int size)
{
    double* celsiusNumbers = (double*)malloc(size);

    for (int i = 0; i < size; i++)
    {
        int celsiusConversion = (fahrenheitReadings[i] - 32) / 1.8;
        celsiusNumbers[i] = celsiusConversion;
    }

    double sum = 0.0;

    for (int i = 0; i < size; i++)
    {
        sum += celsiusNumbers[i];
    }

    return sum / size;
}

華氏温度基準の摂氏平均値を求めるアルゴリズム.

華氏度を摂氏度に変換する過程はN段階

である.

℃の平均温度を求めるために、さらなるプロセスはN段階

である.

N+N=2 Nフェーズ->O(N)

オーバーラップリングはN*N、O(N)²)2個の独立ループ(N+N)がO(N)

7.5服装商標

string* markInventory(string* clothingItems, int size)
{
    string* clothingOptions = new string[size * 5];
    int index = 0;

    for (int i = 0; i < size; i++)
    {
        for (int j = 1; j <= 5; j++)
        {
            clothingOptions[index++] = clothingItems[i] + ": " + to_string(j);
        }
    }

    return clothingOptions;
}

件のシリアル番号を受信し、1〜5のサイズを追加することによって商標テキストシーケンスを作成するアルゴリズム.

Nは服装品種配列の元素数

である.

はドアの重なりであるが、外側forドアはN回、内側forドアは5回N*5=5 Nステップ->O(N)

を繰り返す
7.61世紀

int countOnes(int** arr, int outerSize, int* innerSize)
{
    int count = 0;

    for (int i = 0; i < outerSize; i++)
    {
        for (int j = 0; j < innerSize[i]; j++)
        {
            if (arr[i][j] == 1)
            {
                count += 1;
            }
        }
    }

    return count;
}

という番号の内部アレイサイズの異なる2次元アレイを返すアルゴリズム.

Nはアレイ全体の要素数

である.
ドア

はネストされていますが、実際には要素全体を巡る->O(N)

です.
7.7パリントロム検査器

bool isPalindrome(char* str, int size)
{
    int leftIndex = 0;
    int rightIndex = size - 1;

    while (leftIndex < size / 2)
    {
        if (str[leftIndex] != str[rightIndex])
        {
            return false;
        }

        leftIndex++;
        rightIndex--;
    }

    return true;
}

同じ単語またはフレーズ(回文)であるかどうかを決定するために、前または後ろに読むアルゴリズム.

Nは文字列長

である.

、サイクル数N/2->O(N)

7.8すべての積を求める

int* twoNumberProducts(int* arr, int size)
{
    int productSize = 1;
    for (int i = 2; i <= size; i++)
    {
        productSize += i;
    }
    int* products = new int[productSize];
    int index = 0;

    for (int i = 0; i < size - 1; i++)
    {
        for (int j = i + 1; j < size; j++)
        {
            products[index++] = arr[i] * arr[j];
        }
    }

    return products;
}

2つの数値の組合せに

配列のすべての数値要素を乗算するアルゴリズム.

はドアに重ねられ、外部はドア共N-1回、内部はドアそれぞれN-1、N-2…運転2、1回

合計N²/ステップ2－>O(N)²)

7.8.1複数のデータセットの処理

上のアルゴリズムが、1つのアレイ内のすべての数と別のアレイ内のすべての数との積として計算する場合、

.

for (int i = 0; i < firstSize; i++)
    {
        for (int j = 0; j < secondSize; j++)
        {
            products[index++] = firstArr[i] * secondArr[j];
        }
    }

シナリオ1:5シナリオと5シナリオ

5*5フェーズ25フェーズ

シナリオ2:9シナリオと1シナリオ

9*1ステージ、9ステージ

アレイのサイズがそれぞれNとMの場合O(N*M)

NとMはO(N)に等しい²)

NとMが同時に大きな値ではない(ex>Nの場合O(N))

小数は定数であり、

を省略する.

O(N＊M)はO(N)とO(N)である.²)

の効率
7.9暗号ビスケット

void everyPassword(int n, char* pw, int index)
{
    if (index == n)
    {
        cout << pw << endl;

        return;
    }

    for (int i = 'a'; i <= 'z'; i++)
    {
        pw[index] = i;
        everyPassword(n, pw, index + 1);
    }
}

与えられたすべての長さ文字列の組合せを生成するアルゴリズム

文字26文字が文字列長に重なる->O(26^N)

文字列が1文字の場合26、2文字の場合26*26=676、3文字の場合26*26*26=17576…

O(2^N)必要なステップを1つ追加すると2倍になります

O(26^N)非常に非効率