python - 哪种算法计算字符串中最后一个单词的字符数运行速度更快

Question

对于给定的字符串 s，我想计算计算最后一个单词的字符数所需的时间复杂度。

第一个代码:

count = 0
flag = 0
for i in s[::-1]:
  if (i == ' '):
     if (flag):
       break
  else:
    count += 1
    flag = 1

第二个代码://假设至少有2个单词

def countLast(sen):
  count = 0
  i = -1
  while abs(i) <= len(sen):
    if sen[i] == " ":
      i -= 1
      continue
    else:
      while sen[i] != " ":
        count += 1
        i -= 1
      return count

第一个代码将在 O(n) + O(w) 中运行，其中 n 是字符串中的单词数，因为我使用的是 for 循环中的 [::-1]，w 是最后一个单词的字符数。

我的观点是，第二个代码片段将在 O(w) 中运行，其中 w 是字符数。

这是正确的吗？哪种算法的时间复杂度更低(运行速度更快)？

Answer 1

我首先为您的第一个代码创建了一个函数，如下所示:

def first(s):
    count = 0
    flag = 0
    x = 0
    for i in s[::-1]:
        if (i == ' '):
            if (flag):
                break
        else:
            x += 1
            flag = 1

然后，在 iPython 中我只使用了函数 %timeit 这是结果

In [31]: strings
Out[31]: ['a a', 'a aa', 'a aaa', 'a aaaa', 'a aaaaa', 'a aaaaaa']
In [32]: for s in strings:
    ...:     print("for the first function --> ")
    ...:     %timeit first(s)
    ...:     print("count last function -->" )
    ...:     %timeit countLast(s)
for the first function -->
272 ns ± 2.27 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
count last function -->
310 ns ± 3.9 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
for the first function -->
331 ns ± 13.9 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
count last function -->
437 ns ± 45.5 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
for the first function -->
380 ns ± 8.15 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
count last function -->
456 ns ± 2 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
for the first function -->
434 ns ± 6.32 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
count last function -->
540 ns ± 5.5 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
for the first function -->
496 ns ± 13.1 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
count last function -->
649 ns ± 15 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
for the first function -->
542 ns ± 11.8 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
count last function -->
751 ns ± 30.7 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

所以，第一个函数似乎更快