算法 : explanation about complexity and optimization

Question

我正试图在网络上找到一两个以简单术语解释这些内容的资源。此外，这个概念能否以实用的方式用于改进算法？如果是这样，如何？以下是我从联系人那里得到的简要说明。

I dont know where you can find simple explanation. But i try to explain you. Algorithm complexity is a term, that explain dependence between input information and resourses that need to process it. For example, if you need to find max in array, you should enumerate all elements and compare it with your variable(e.g. max). Suppose that there are N elements in array. So, complexity of this algorithm is O(N), because we enumerate all elements for one time. If we enumerate all elements for 2 times, complexity will be O(N*N). Binary search has complexity O(log2(N)), because its decrease area of search by a half during every step. Also, you can figure out a space complexity of your algorithm - dependence between space, required by program, and amount of input data.

Answer 1

很难说出关于复杂性的所有事情，但我认为 wiki 对此有很好的解释并且对于启动很好，请参阅:

1. Big O notation用于介绍这方面(你也可以看看teta 和 omega 符号)。
2. Analysis of algorithm , 知道更多关于复杂性。
3. 和Computational Complexity ,这是计算机中的一个大理论科学。

关于优化你可以看web和wiki找到它，但是五行你的 friend 给了一个很好的例子来介绍，但这些不是一夜之间了解它们的用法，计算和千理论的努力。

总而言之，您可以根据需要熟悉它们，阅读 wiki，更深入地阅读书籍，如 Gary and Johnson或阅读 Computation Complexity, a modern approach ，但不要指望在那之后你就知道关于他们的一切。你也可以看到这个讲义:http://www.cs.rutgers.edu/~allender/lecture.notes/ .