在时间复杂度方面计算算法效率的步骤是什么

Question

我忘记了如何计算算法的时间复杂度.我不是在寻找一本书或30页的博客来刷新这些知识.采用以下算法,请您按照我计算时间复杂度的方式进行校正.谢谢

线性搜索

bool SeqSearch(int[] arr, int sValue) {
    for (int index = 0; index < arr.Length-1; index++)
    if (arr[index] == sValue)
        return true;
    return false;
}

使用的步骤和逻辑

1. 遍历所有元素 - N
2. 每个指数的比较 - 1或者是它N
3. 返回真或假 - 1

最后

我忘记了我们添加它们还是我们将它们相乘？我认为我们必须添加所以最终结果, N+N+1所以这一定是一个大哦!N.O(N)

问题

1. 我是否将每个步骤所花费的时间相乘或加起来
2. 为了进行比较,无法确定何时结束.那么什么是时间(我假设为1因为它可能在第一个索引处找到,N否则作为最后一个索引)
3. 作业和回归是恒定时间1？

注意:请不要将我转介到网站.SO会保持很长时间,那些有相同/类似问题的人肯定会发现这篇文章的答案很有用.我不能相信其他网站将被删除等.此外,我并不担心效率,时间复杂性,而是用于找到它的过程/步骤.

资源

http://faculty.simpson.edu/lydia.sinapova/www/cmsc250/LN250_Weiss/L03-BigOh.pdf

我只是想把这个链接放到pdf上,这清楚地解释了如何解释什么语句和何时.就像我想要的那样.

Answer 1

考虑原始操作(存储器访问和算术/逻辑操作).

根据输入的大小计算它们的算法N(arr.Length在您的情况下).

然后看看操作总数是如何相关的N,是否只是某个常数或多项式N(例如N³)或对数N或指数N或其他.

如果它看起来像N+1或2*N,你应该忽略小常数,因为你主要关心的是当N大的时候发生什么以及整体行为.

这是基础知识.

这是最坏情况下的大致时间复杂度(何时sValue不在arr[]):

int index = 0; 是1

index < arr.Length-1;重复arr.Length次数是1(但可能达到,比方说,10)

index++重复arr.Length次数为1(但最多可能是3 次)

if (arr[index] == sValue)重复arr.Length次数是1(但可能达到,比方说,10)

return value; 是1

所以你有一些像1 + 1*arr.Length+ 1*arr.Length+ 1*arr.Length= 1 + 3*arr.Length+ 1的东西.你将其简化为arr.Length,因此O(N).

平均而言,您只有arr.Length2次迭代.因此,平均而言,你有1 + 1*arr.Length/ 2 + 1*arr.Length/ 2 + 1*arr.Length/ 2 + 1 = 2 + 1.5*arr.Length.再次,O(N).

但你应该真的读到这些东西.