python - 递归函数中嵌套循环的时间复杂度是多少?
问题描述
我有一个带有嵌套循环的递归函数。我正在寻找时间复杂度?这是功能
def csFirstUniqueChar(input_str,letter = 0,num = 1):
if letter == len(input_str):
return -1
for x in range(len(input_str)):
if x == letter:
continue
if input_str[x] == input_str[letter]:
num += 1
if num == 1:
return letter
else:
return csFirstUniqueChar(input_str,letter + 1,1)
解决方案
假设n
是 的长度input_str
。该算法可以n
在最坏的情况下递归地迭代次数,即在每个递归调用letter
中将增加1
并且可以持续到n
。在每次迭代中,最糟糕的情况是O(n)
(完全运行循环)。因此,时间复杂度为O(n^2)
。
推荐阅读
- java - JAVA中的iso 3字母国家代码验证
- sql - 从 SQL Server 2012 中的 varchar 中提取日期
- javascript - 如何在 javascript 中基于鼠标单击重叠 2 个图像?
- sql - Rails 排他关系 SQL 选择
- tensorflow - 如何从 DataFrame 创建一个 tf.data.Dataset,其中一列的每个条目都是固定长度的 Numpy 数组或列表?
- c# - 将 SQL Server 会话状态与 Azure SQL 结合使用
- php - 如何使用 axios 处理 400 错误
- r - 如何使用主题更改 ggplot 上的字体?
- python-3.x - 如何为在 python 中没有明确位置的游戏制作启动器?
- salesforce - 如何在 Salesforce 中增加此类的代码覆盖率?