代码优化说明

优化和解释 C++ 代码，重点关注时间复杂度。

在对 Cloud 控制台使用不同参数值时，或通过直接调用 Vertex AI API，您可以直接查询模型，并测试返回的结果。

系统指令

您是一位热衷于优化代码的 C++ 程序员。优化所提供的代码后，您需要说明时间复杂度的变化和改进。

提示Freeform

我有一个 C++ 代码，用于输出字符在字符串中出现的次数，但有人告诉我这种做法效率不高。

您能否使用地图提高效率？

#include <iostream>
#include <string>

using namespace std;

int main() {
  string input;
  cout << "Enter a string: ";
  getline(cin, input);

  for (int i = 0; i < input.length(); ++i) {
    char current_character = input[i];
    int count = 0;
    for (int j = 0; j < input.length(); ++j) {
      for (int k = 0; k < input.length(); ++k) {
        if (input[j] == current_character && j == k) {
          ++count;
        }
      }
    }

    bool already_printed = false;
    for (int k = 0; k < i; ++k) {
      if (input[k] == current_character) {
        already_printed = true;
        break;
      }
    }

    if (!already_printed) {
      cout << current_character << ": " << count << endl;
    }
  }

  return 0;
}

响应

原始代码的时间复杂度为 O(n³)，其中 n 是输入字符串的长度。这是因为嵌套循环：外层循环会迭代每个字符，第二个循环会迭代每个字符的整个字符串，第三个循环（虽然看似多余）在最坏的情况下仍会迭代字符串的长度。对 already_printed 进行额外的循环检查会增加另一个 O(n) 因子，但其重要性不如嵌套循环。

以下优化后的代码使用 std::map 实现了 O(n log n) 的时间复杂度。log n 因子来自映射的插入和查找操作（通常使用平衡二叉搜索树实现）。

#include <iostream>
#include <string>
#include <map>

using namespace std;

int main() {
  string input;
  cout << "Enter a string: ";
  getline(cin, input);

  map<char, int> char_counts;
  for (char c : input) {
    char_counts[c]++;
  }

  for (auto const& [key, val] : char_counts) {
    cout << key << ": " << val << endl;
  }

  return 0;
}

改进说明：

  1. 使用 std::map：原始代码会多次重复计算每个字符的出现次数，效率不高。std::map（或 std::unordered_map，平均性能可能更快，但最坏情况下略高）会将每个字符存储为键，并将其计数存储为值。这样可以避免重复计数。

  2. 迭代一次：经过优化的代码仅迭代一次输入字符串，以填充 char_counts 映射。与原始代码的嵌套循环相比，这可以显著减少操作次数。

  3. 高效统计字符数：char_counts[c]++; 行会高效地增加每个字符的计数。如果该字符尚未添加到映射中，则会以 1 的计数添加该字符；否则，其现有计数会递增。

  4. 消除冗余检查：由于原始代码的计数方法效率低下，因此需要进行 already_printed 检查。std::map 固有地处理此问题；每个字符只会计数一次，最后一个循环会遍历映射，输出每个字符及其计数。

总而言之，经过优化的代码将时间复杂度从 O(n³) 降低到 O(n log n)，从而显著提高了效率。对于较大的输入字符串，这种差异会非常明显。使用 std::unordered_map 可以进一步将平均性能提升到 O(n)，但代价是极端情况的性能略有提高。选择取决于具体应用以及最差性能是否是关键问题。
型号： gemini-1.5-flash-002
温度： 0.2
输出令牌数量上限： 8192
TopK： 40.0
TopP： 0.95