关于代码段的时间复杂度

道伊

我正在尝试解决有关Pramp的问题

实现功能reverseWords,以最有效的方式反转数组中单词的顺序。

例如:arr = ['p','e','r','f','e','c','t','','m','a','k','e ','s',',','p','r','a','c','t','i','c','e']

输出:['p','r','a','c','t','i','c','e',',','m','a','k', 'e','s',',','p','e','r','f','e','c','t']

他们提供的类似Python的伪代码如下:

function reverseWords(arr):
    # reverse all characters:
    n = arr.length
    mirrorReverse(arr, 0, n-1)

    # reverse each word:
    wordStart = null
    for i from 0 to n-1:
        if (arr[i] == ' '):
            if (wordStart != null):
                mirrorReverse(arr, wordStart, i-1)
                wordStart = null
        else if (i == n-1):
            if (wordStart != null):
                mirrorReverse(arr, wordStart, i)
        else:
            if (wordStart == null):
                wordStart = i

    return arr


# helper function - reverses the order of items in arr
# please note that this is language dependent:
# if are arrays sent by value, reversing should be done in place

function mirrorReverse(arr, start, end):
    tmp = null
    while (start < end):
        tmp = arr[start]
        arr[start] = arr[end]
        arr[end] = tmp
        start++
        end--

他们说时间复杂度为O(n),这主要是因为他们两次遍历数组,并且每一项的动作数均恒定碰巧的是,我想出了stringstreams在C ++中使用的完全相同的方法,但是认为它效率不高!

我认为此代码段的时间复杂度应为O(mn),其中m字符串中的单词n数和每个单词中字母的平均数。之所以如此,是因为我们遍历了输入中的所有元素,并且在最坏的情况下mirrorReverse(),对于给定的,再次访问所有元素进行反转i

哪个是对的?

修剪

O(n)中n是指输入的长度(总字符),而不是单词的数量。我怀疑您感到困惑,因为代码n在后一种意义上使用了变量

注意说明:“遍历数组...”。“数组”由单个字符组成。

对我来说,实现似乎有点愚蠢。更具可读性:

  1. 将字母组组合成单词。
  2. 用平凡的列表片反转单词顺序(包括空格)。
  3. 将单词扩展回字符。

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章