Perangkap biasa dan strategi pengoptimuman kerumitan masa C++

Adalah penting untuk memahami perangkap kerumitan masa termasuk: 1. Gunakan algoritma yang betul 2. Kurangkan salinan yang tidak perlu; Contoh praktikal meneroka kaedah pengoptimuman untuk mengira jumlah kuasa dua tatasusunan, menukar rentetan kepada huruf besar dan mencari elemen dalam tatasusunan tidak tertib.

Perangkap biasa dan strategi pengoptimuman dalam kerumitan masa C++

Perangkap kerumitan masa biasa:

• Kod kompleks yang tersembunyi mungkin lebih kompleks: Sebagai contoh, kod yang kelihatan menggelung sekali mungkin sebenarnya menggelung setiap elemen dalam tatasusunan.
• Penyalinan yang tidak perlu: Menyalin struktur data yang besar akan membawa kepada peningkatan kerumitan masa.
• Traversal tak tertib: Kerumitan masa merentasi struktur data tak tertib adalah lebih tinggi, terutamanya apabila jumlah data adalah besar.

Strategi pengoptimuman:

• Gunakan algoritma yang betul: Fahami kerumitan masa algoritma yang berbeza dan pilih struktur data dan algoritma yang paling sesuai dengan masalah.
• Kurangkan salinan yang tidak diperlukan: Elakkan parameter lulus mengikut nilai dan gunakan rujukan atau penunjuk terlebih dahulu.
• Optimumkan traversal: Isih data atau menggunakan indeks boleh meningkatkan masa traversal dengan ketara.

Kes praktikal:

Perangkap: Tujuan kod berikut adalah untuk mengira jumlah kuasa dua setiap elemen dalam tatasusunan.

int main() {
  int n;
  cin >> n;
  int arr[n];
  for (int i = 0; i < n; i++) {
    cin >> arr[i];
  }
  int sum = 0;
  for (int i = 0; i < n; i++) {
    sum += pow(arr[i], 2);
  }
  cout << sum << endl;
  return 0;
}

Masalah: Kod yang kelihatan hanya gelung sekali sebenarnya menggelung melalui setiap elemen dalam tatasusunan dua kali: sekali untuk input dan sekali untuk mengira jumlah petak.

Pengoptimuman: Optimumkan kod ini dengan mengira jumlah kuasa dua dalam peringkat input secara serentak.

int main() {
  int n;
  cin >> n;
  int arr[n];
  int sum = 0;
  for (int i = 0; i < n; i++) {
    cin >> arr[i];
    sum += pow(arr[i], 2);
  }
  cout << sum << endl;
  return 0;
}

Perangkap: Kod berikut menukar rentetan kepada huruf besar.

string toUpperCase(string s) {
  int n = s.length();
  for (int i = 0; i < n; i++) {
    s[i] = toupper(s[i]);
  }
  return s;
}

Masalah: Kod ini menyalin rentetan pada setiap lelaran.

Pengoptimuman: Gunakan parameter rujukan untuk mengelakkan salinan yang tidak diperlukan.

void toUpperCase(string& s) {
  int n = s.length();
  for (int i = 0; i < n; i++) {
    s[i] = toupper(s[i]);
  }
}

Perangkap: Kod berikut mencari elemen dalam tatasusunan tidak tertib.

int findElement(int arr[], int n, int x) {
  for (int i = 0; i < n; i++) {
    if (arr[i] == x) {
      return i;
    }
  }
  return -1;
}

Masalah: Kerumitan masa merentasi tatasusunan tidak tertib ialah O(n).

Pengoptimuman: Optimumkan kod ini dengan mengisih tatasusunan, sekali gus mengurangkan kerumitan masa kepada O(log n). rreeee

Atas ialah kandungan terperinci Perangkap biasa dan strategi pengoptimuman kerumitan masa C++. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!