写big O notation时可以使用未知变量吗？
When writing big O notation can unknown variables be used?
我不知道我在标题中使用的语言是否正确，但这里有一个例子可以说明我的问题。
这个从字符串中删除字符对的 non-optimal 算法的时间复杂度是多少？
该函数将循环遍历一个字符串。当它发现两个彼此相邻的相同字符时，它将 return 一个没有找到的对的字符串。然后它递归地调用自己直到没有找到对。
示例（每一行都是来自一个递归函数调用的 return 字符串）：
iabccba
iabba
iaa
i
将时间复杂度描述为 O(|Characters| * |Pairs|) 是否公平？
O(|Characters|^2) 可以使用对来描述时间复杂度吗，即使在初始函数调用时对的数量是未知的？
有人争辩说这个算法是O(n^2)因为对的数量是未知的。
你是对的，严格来说这是O(|Characters| * |Pairs|)
然而，在最坏的情况下，对的数量可以与字符的数量相同（或相同的数量级），例如在字符串 'abcdeedcba' 中
因此，将其描述为 O(n^2) 最坏情况也是有道理的。
我认为这在很大程度上取决于您要解决的问题及其定义。
例如，对于图算法，每个人都可以接受复杂度 O(|V| + |E|) 的写作，尽管在密集图的最坏情况下 |E| = |V|^2。在其他问题中，我们只考虑最坏的情况并写成 O(n^2)，而没有将其分解为更具体的变量。
我想说，如果没有特殊约定，或者问题中没有关于对数的特殊数据，O(...) 意味着最坏情况下的性能，因此 O(n^2) 会更合适。
我不知道我在标题中使用的语言是否正确，但这里有一个例子可以说明我的问题。
这个从字符串中删除字符对的 non-optimal 算法的时间复杂度是多少？
该函数将循环遍历一个字符串。当它发现两个彼此相邻的相同字符时，它将 return 一个没有找到的对的字符串。然后它递归地调用自己直到没有找到对。
示例（每一行都是来自一个递归函数调用的 return 字符串）：
iabccba
iabba
iaa
i
将时间复杂度描述为 O(|Characters| * |Pairs|) 是否公平？
O(|Characters|^2) 可以使用对来描述时间复杂度吗，即使在初始函数调用时对的数量是未知的？
有人争辩说这个算法是O(n^2)因为对的数量是未知的。
你是对的，严格来说这是O(|Characters| * |Pairs|)
然而，在最坏的情况下，对的数量可以与字符的数量相同（或相同的数量级），例如在字符串 'abcdeedcba' 中
因此，将其描述为 O(n^2) 最坏情况也是有道理的。
我认为这在很大程度上取决于您要解决的问题及其定义。
例如，对于图算法，每个人都可以接受复杂度 O(|V| + |E|) 的写作，尽管在密集图的最坏情况下 |E| = |V|^2。在其他问题中，我们只考虑最坏的情况并写成 O(n^2)，而没有将其分解为更具体的变量。
我想说，如果没有特殊约定，或者问题中没有关于对数的特殊数据，O(...) 意味着最坏情况下的性能，因此 O(n^2) 会更合适。