以下代码的时间复杂度

本文关键字：时间复杂度 代码 | 更新日期: 2023-09-27 18:24:07

我正在尝试检查以下简单程序的时间复杂度。该程序将字符串中的空格替换为 '%20' 。

  1. 计算空间的循环(O(1( 时间(

        foreach (char k in s)
    {
        if (k == ' ')
        {
            spaces_cnt++;
        }
    }

  2. 用于替换空格的循环(O(n(，其中 n 是字符串的大小(

        char[] c = new char[s.Length + spaces_cnt * 3];
    int i = 0;
    int j = 0;
    while (i<s.Length)
    {
        if (s[i] != ' ')
        {
            c[j] = s[i];
            j++;
            i++;
        }
        else
        {
            c[j] = '%';
            c[j + 1] = '2';
            c[j + 2] = '0';
            j = j + 3;
            i++;
        }
    }

所以我猜这是一个"O(n( + O(1("解决方案。如果我错了，请纠正我。

以下代码的时间复杂度

循环计算空格需要O(n)，而不是O(1)，因为您正在迭代并执行检查字符串中n字符。

正如您所说，更换循环需要O(n).按顺序执行的两个O(n)操作的组合复杂度为 O(n)(常数因子在 Big-O 表示法中被丢弃(。

附言您知道您可以使用一行实现所有代码的等效值吗？

s = s.Replace(" ", "%20");

看起来您正在尝试对字符串进行编码。 如果是这种情况，您可以使用 UrlPathEncode(( 方法。 如果您只是尝试对空格进行编码，请使用 Replace(((如 Douglas 所述(。

相关文章：