以下大O是if statement什么？
if "pl" in "apple":
...
如果字符串"pl"在字符串"apple"中找到,python如何确定的总体大O是多少？
或字符串搜索中的任何其他子字符串.
这是测试子字符串是否在字符串中的最有效方法吗？它使用相同的算法.find()吗？
假设我们有以下两个列表:
L1 = [1, 2, 3, 4, 5] and L2 = [4, 5, 1, 2, 3]
这些可以被认为是相同的,因为L1两个索引向右的旋转将在L2中产生.
这个解决方案很简单,只需每次将列表旋转1,直到它与L2匹配,我想弄清楚的是,如果可以通过找到某种模式或方程来确定这两个列表是否相同当两个列表插入输出时是相同的数字,因此表明列表实际上是相同的(就圆形而言).
这可能吗？或者这是否涉及高级数学？
编辑:不试图找到确定圆度或最少计算量的最快方法.我试图找出列表是否可以量化为具有相同圆度的不同列表具有相同的签名,因此列表被认为是相同的.有没有可以解决这个问题的函数或方程？即
f(L1) = X and f(L2) = X
由于X = X,这两个列表是圆形相同的.
我有问题的特殊情况,但是知道是否可以使用任何函数会很好.
所以我想在字符串中找到子字符串的位置.好的,在python中有一个find方法可以完全满足需要.
string.find(s,sub [,start [,end]])
返回s中找到substring sub的最低索引,使sub完全包含在s [start:end]中.失败时返回-1.开始和结束的默认值以及负值的解释与切片的默认值相同.
惊人的,但问题是,在一个大的字符串找到一个大子可以从运行O(n*m)到O(n)(这是一个巨大的交易)取决于算法.文档不提供有关时间复杂度的信息,也不提供有关基础算法的信息.
我看到如何解决这个问题的方法很少:
两者听起来都不容易(我希望有一种更简单的方法).那么如何才能找到内置函数的复杂性？
假设我有任意类型的数据集{A,B,C,D},我想将它与另一个数据集进行比较.我想比较{A,B,C,D},{B,C,D,A},{C,D,A,B}和{D,A,B,C},但是不适用于{A,C,B,D}或任何其他类似订购的套装.什么是快速的方法呢？
将它们存储在数组中,旋转并以这种方式进行比较是一个O(n ^ 2)任务,因此不是很好.
我的第一个直觉是将数据存储为像{A,B,C,D,A,B,C}这样的集合,然后搜索只有O(n)的子集.这可以更快地完成吗？