程序的整体时间复杂度? [英] overall time complexity of the program?

问题描述

假设您在数组中采用"n"个输入(为此，您必须运行一个循环，对"n"个不同的位置进行"n"次迭代)，这将具有O(n)的复杂度.

suppose you take 'n' inputs in an array(and for that you have to run a loop that iterates 'n' times for 'n' different locations), which would have O(n) complexity.

然后您尝试执行O(log n)或小于O(n)时间复杂度的运算. 我的问题是，使这些运算的复杂度小于O(n)真的很重要，因为整个程序的时间复杂度至少为O(n).

And then you you try to perform operations that have O(log n) or less than O(n) time complexity. my question here is that does it really matter to have complexity of those operations less than O(n) since your whole program will have atleast O(n) time complexity. 

推荐答案

实际上，程序的时间复杂度可能由读取输入所花费的时间决定.例如，如果程序从输入中读取一个数组，然后在该数组中执行一个二进制搜索，则时间复杂度仅为Θ(n)，这仅仅是因为读取了输入.

Indeed, a program's time complexity could be dominated by the time it takes to read the input. For example, if a program reads an array from input, then does one binary search in that array, the time complexity is Θ(n) simply because of reading the input.

程序的时间复杂度也可能由生成输出所花费的时间所控制.例如，具有n个顶点的树具有n-1个边，因此树上的许多算法都可以在Θ(n)时间内运行；但是，如果我们要打印邻接矩阵，则没有比Θ更好的方法了(n ² )时间，因为输出是具有n ² 个元素的2D数组.

A program's time complexity could also be dominated by the time it takes to generate the output. For example, a tree with n vertices has n-1 edges, so many algorithms on trees can run in Θ(n) time; but if we want to print the adjacency matrix then there's no way to do that in better than Θ(n²) time because the output is a 2D array with n² elements.

我认为存在一个隐式的后续问题:那么一个算法如何能在不到Θ(n)的时间内运行?请注意，以上所讨论的是执行 IO .二进制搜索算法要花费Θ(logn)时间，因为二进制输入搜索算法本身并不完成输入的读取.算法只是程序的一部分；数组是由程序的不同部分从输入中读取的，因此在运行算法之前它就存在于内存中，并且该算法可以通过

I think there's an implicit follow-up question: so how can an algorithm ever run in less than Θ(n) time? Note that the above is talking about programs which do IO. The binary search algorithm takes Θ(log n) time, because reading the input is not done by the binary search algorithm itself. An algorithm is only part of a program; the array is read from input by a different part of the program, so it exists in memory before the algorithm is run, and the algorithm gets access to it via a reference. That means the algorithm receives its input, of size n, in Θ(1) time.

这篇关于程序的整体时间复杂度?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！