关于计算复杂性理论的问题 [英] Question about Computational Complexity Theory

问题描述

1.如何计算一种算法的运行时间复杂度? ()通过一个简单的示例进行说明.
2.算法中输入大小的含义是什么?
3.什么是算法的最佳情况，最差情况，平均情况?
4. big-o表示法的目的是什么?

在此先谢谢您！ http://en.wikipedia.org/wiki/Analysis_of_algorithms [^ ]包含您需要的所有信息.

将来，请尝试至少自己进行基础研究，不要浪费我们和您的时间.

您真的想阅读以下Wikipedia文章: ^ ].

输入大小的含义取决于正在分析的具体算法.

有关最佳情况，更糟情况，平均情况" 的定义，请参见所引用的文章.

简短示例:
在长度为n的列表的末尾附加一个节点.
空间复杂度:n(我们需要n + 1个元素的空间，常数1以大O表示法丢弃
时间复杂度:n(如果没有指向列表末尾的指针，则必须遍历整个列表，因此n)
时间复杂度:1(如果我们确实有一个指向列表末尾的指针(例如队列)，我们可以直接去那里，需要用1表示的恒定时间).

示例2:最坏的情况
如果已对插入的值进行排序，则将值插入不平衡的二叉树会导致退化的树(实际上是链表).
在最坏的情况下，时间复杂度从O(log ₂ n)变为O(n).

大O表示法的目的是对算法的计算复杂度进行分类，以使其在性能上具有可比性.有时，可以通过权衡其他复杂性来调整算法.假设具有恒定空间的算法的运行时为O(n ² )运行时，有时可能通过增加算法的空间复杂度来获得次指数运行时.

希望我能为您阐明这一点.

问候，

曼弗雷德(Manfred)

1. How does one calculate the run time complexity of an algorithm? ()lease explain with a simple example.
2. What is meaning of size of input in algorithm?
3. What is bestcase,worsecase,averagecase of an algorithm?
4. What is purpose of big-o notation?

Thanks in advance!

解决方案

A very simple google lead straight to Wiki: http://en.wikipedia.org/wiki/Analysis_of_algorithms[^] which contains all of the info you need.

In future, please try to do at least basic research yourself, and not waste our time and yours.

You really want to read this Wikipedia article: Computational complexity theory[^].

The meaning of input size depends on the concrete algorithm that is being analysed.

For the definition of "bestcase,worsecase,averagecase" please see the referenced article.

Short example:
Appending a node at the end of a list of length n.
Space complexity: n (We need space for n + 1 elements, the constant 1 is dropped in big O notation
Time complexity: n (If we don''t have a pointer to the end of the list we have to traverse the whole list thus n)
Time complexity: 1 (If we do have a pointer to the end of the list (like a queue for instance) we can go there directly and need constant time denoted by 1)

Example 2: Worst case
Inserting values into an unbalanced binary tree can cause a degenerated tree (actually a linked list) when the values inserted were already sorted.
The time complexity goes from O(log₂n) to O(n) in the worst case.

The purpose of the big O notation is to categorize the computational complexity of algorithms to make them comparable performance wise. Sometimes algorithms can be tuned by trading on complexity off for another. Lets say the runtime of an algorithm with constant space is O(n²) runtime wise it is sometimes possible to get a sub exponential runtime by increasing the space complexity of the algorithm.

Hope I could shed some light onto this for you.

Regards,

Manfred

这篇关于关于计算复杂性理论的问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！