算法复杂度
我正在尝试计算以下算法的复杂度，
private static List<int> GetIndexes(string strippedText, string searchText)
{
List<int> count = new List<int>();
int index = 0;
while (strippedText.Length >= index && index != -1)
{
index = strippedText.IndexOf(searchText.Trim(), index,
StringComparison.OrdinalIgnoreCase);
if (index != -1)
{
count.Add(index);
index++;
}
else continue;
}
return count;
}
我知道如果 count 在每次迭代中增加 1，则循环的复杂度为 O(n) ，但是增量取决于找到的索引。在每次迭代中，它可以增加 1 或 strippedText.lenght()。
有什么想法吗？
I am trying to calculate the complexity of the following algorithm
private static List<int> GetIndexes(string strippedText, string searchText)
{
List<int> count = new List<int>();
int index = 0;
while (strippedText.Length >= index && index != -1)
{
index = strippedText.IndexOf(searchText.Trim(), index,
StringComparison.OrdinalIgnoreCase);
if (index != -1)
{
count.Add(index);
index++;
}
else continue;
}
return count;
}
I know that the loop has a complexity of O(n) if count increments by 1 on each iteration but, the increments depends from the indexes found. on each iteration it could increment 1 or strippedText.lenght().
Any idea?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（7）
尽管如此，最坏的情况仍然是 O(n)。
Still, the worst case is O(n).
它仍然是
O(n)- 这是因为它的渐近增长速度与O(n)大 O 表示法用于算法增长的上限- 也就是说，算法保证以与它相同或更慢的速度增长的函数。
在平均情况下，您的算法将以
O(n/m)的速度增长，其中m是对字符串中索引密度的估计（0 = 无索引） , 1 = 每个字符的索引）。假设在n上大致恒定，您可以忽略m并且仍然说该算法为O(n)。事实上，在现实世界中，您的算法几乎肯定会比
O(n)更快，但这并不能阻止它开始一个O(n)函数。查看此页面，特别是：
It is still
O(n)- this is because it grows asymptotically at the same rate asO(n)Big O notation is used for the upper-bound of algorithmic growth - that is, it's a function that the algorithm is guaranteed to grow at the same rate as, or slower than.
In the average case your algorithm will grow at rate
O(n/m)wheremis some estimate of the how dense the indexes are in your strings (0 = no indexes, 1 = index at every character). Assuming that's roughly constant overnyou can ignore themand still say the algorithm isO(n).The fact that, in the real world, your algorithm will almost certainly be faster than
O(n)doesn't stop it begina nO(n)function.Take a look at this page, particularly:
O(n)，其中 n 是 strippedText 字符串的长度。
最坏的情况，每个字符都等于 searchText 并会导致 n 次迭代，但即使情况并非如此（我假设不会），您的平均情况将是 n 的某个因子 c其中 c 大于 0 但小于 1，因此循环次数将为 cn，但常数因子 n 仍将表示为 O(n)。
O(n) where n is the length of the strippedText string.
Worst case, every character will be equal to the searchText and will result in n itterations, but even if that isn't the case (which I am assuming it won't be) your average case will be some factor, c, of n where c is greater than zero but less than 1, so the number of loops will be cn, but a constant factor of n will still be represented as O(n).
我仍然会说它是 O(n) （或者至少是最坏的 O(n)，除非你的索引可以小于 -1（比如 -10），这会进一步重置它）
但是是的 O(n)。
I would still say that it is O(n) (or at least At worst O(n), unless your index can be made less than -1 say -10, which would reset it further)
But yes O(n).
实际上它是 O(strippedText.Length*searchText.Length)，因为索引对 searchText 和 strippedText 中的字符进行比较。
Actually it's O(strippedText.Length*searchText.Length) since index of makes a comparison between characters in searchText and strippedText.
这完全取决于字符串
IndexOf()方法的实现方式。基本上，您只需使用 IndexOf() 搜索整个字符串 - 其效率取决于该方法的效率。有几种不同复杂度的字符串搜索算法，范围从
O(m+n)到O(m*n)（m和n是两个字符串的长度）。It all depends on how the strings
IndexOf()method is implemented. Basically you just search through the whole string withIndexOf()- how efficient that is depends on the efficiency of that method.There are several string search algorithms of different complexities ranging from
O(m+n)toO(m*n)(mandnbeing the length of the two strings).我想说的是
O(n/m)其中strippedText.Length == n和m是前缀的长度code>searchText是searchText的后缀（如果不存在这样的前缀，则为searchText的长度）。示例：
searchText = 'ababab' --> m == 2
searchText = 'aaaaaa' --> m == 1
searchText = 'abcabc' --> m == 3
searchText = 'abcdefg' -->米==7
I'd say that it's
O(n/m)wherestrippedText.Length == nandmis the length of a prefix ofsearchTextthat is a suffix ofsearchText(if no such prefix exist it's the length ofsearchText).Examples:
searchText = 'ababab' --> m == 2
searchText = 'aaaaaa' --> m == 1
searchText = 'abcabc' --> m == 3
searchText = 'abcdefg' --> m == 7