561
个编辑
更改
→Measuring the size of an instance测量实例的大小
To measure the difficulty of solving a computational problem, one may wish to see how much time the best algorithm requires to solve the problem. However, the running time may, in general, depend on the instance. In particular, larger instances will require more time to solve. Thus the time required to solve a problem (or the space required, or any measure of complexity) is calculated as a function of the size of the instance. This is usually taken to be the size of the input in bits. Complexity theory is interested in how algorithms scale with an increase in the input size. For instance, in the problem of finding whether a graph is connected, how much more time does it take to solve a problem for a graph with 2n vertices compared to the time taken for a graph with n vertices?
To measure the difficulty of solving a computational problem, one may wish to see how much time the best algorithm requires to solve the problem. However, the running time may, in general, depend on the instance. In particular, larger instances will require more time to solve. Thus the time required to solve a problem (or the space required, or any measure of complexity) is calculated as a function of the size of the instance. This is usually taken to be the size of the input in bits. Complexity theory is interested in how algorithms scale with an increase in the input size. For instance, in the problem of finding whether a graph is connected, how much more time does it take to solve a problem for a graph with 2n vertices compared to the time taken for a graph with n vertices?
为了衡量解决一个计算问题的难度，人们可能希望知道最佳算法需要多少时间来解决这个问题。但是，运行时间通常取决于实例。特别是，较大的实例将需要更多的时间来解决。因此，解决一个问题所需的时间（或所需的空间，或任何复杂程度的度量）被计算为实例大小的函数。这通常被认为是以比特为单位的输入大小。复杂度理论关心的是算法如何随着输入大小的增加而伸缩。例如，在求一个图是否连通的问题中，一个2n个顶点的图比一个有n个顶点的图要多花多少时间？