如何分析这个算法的复杂度？

Question

我在看一本关于算法的书，有这样的算法：

let differentCases = (arr:string[])=>{

 arr.forEach(x=>{
 
  console.log(x.toUpperCase())
  console.log(x.toLowerCase())


})
  
}

书上说这个算法的复杂度是O(N)，其中N是arr长度。并表示每个内部函数（例如 toUpperCase）的复杂度都是 O(1)。

但是我有这样的疑问。

如果我采用 toUpperCase 并单独分析它，当 M 是我们要转换为大写的字符串长度值时，时间复杂度将是 O(M)，对吧？

那么为什么在循环中它被认为是O(1)？

Answer 1

首先我认为您粘贴的代码有错误，这就是我在书中的图像

let differentCases = (arr:string[])=>{
 arr.forEach(x=>{
  console.log(x.toUpperCase())
  console.log(x.toLowerCase())
 })
}

如果我采用 toUpperCase 并单独分析它，当 M 是我们要转换为大写的字符串长度值时，时间复杂度将是 O(M)，对吧？

是的，绝对是。

那么为什么在循环中它被认为是O(1)？

我在这里唯一的解释是，本书假设

arr:string[]

中包含的每个字符串都有 1 个单个字符。

但是我同意你的观点，没有这样的前提条件，这段代码的时间复杂度是

O(n) * O(m)

，其中

m

是

arr

中最长字符串的长度。

let differentCases = (arr:string[])=>{
 arr.forEach(x=>{ // O(n)
  console.log(x.toUpperCase()) // O(m)
  console.log(x.toLowerCase()) // O(m)
 })
}

另一种方法

给定

m = m1 + m2 + ... + mn

，其中

mi

是

i-th

中

arr

字符串的长度。

那么时间复杂度可以定义为

O(n) + O(m) 

为什么是

O(n) + O(m)

而不是

O(m)

？

你不能只考虑 O(m)，因为

n

可能比

m

增长得更快。

为什么？让我们考虑一下极端情况，其中

arr

包含 1 个空字符串。

现在：

• n = 1
• 米=0

这意味着：算法将执行该块 1 次

arr.forEach(x=>{
    console.log(x.toUpperCase()) 
    console.log(x.toLowerCase()) 
})

现在让我们考虑

arr

包含 2 个空字符串的情况。

现在：

• n = 2
• 米=0

这意味着：算法将执行该块 1 次

arr.forEach(x=>{
    console.log(x.toUpperCase()) 
    console.log(x.toLowerCase()) 
})

一般来说，forEach主体执行的次数随n线性增长。

因此，即使 m = 0（换句话说，所有字符串的长度均为 0），算法的复杂性仍然会增加。

这就是为什么时间复杂度是 O(n) + O(m)