time - 如何计算这段代码的时间复杂度？它会是什么？

Question

时间复杂度是多少？这是需要找到复杂性的代码：我主要无法理解递归部分：/

void xyz(int n)
{
    for (int i=0;i<n;i++)
      do something;
    if (n)
      for (int i=0;i<n;i++)
        xyz(n-1);
    else return;
}

Answer 1

As someone commented on your question, watch your use of n and i. if(n) will always evaluate to true if n > 0. Also, currently the nesting seems like it might be off, try using brackets to make it clearer.

The general idea for calculating time complexity is to count (mathematically, not manually) how many times the basic operation (the most time-consuming operation, usually the most time-consuming operation inside the deepest nested loop) and seeing how the complexity (number of times the basic operation is done) relates to the input size.

If the time complexity increases at the same speed as the input size increasing, it's linear, or in the complexity class O(n). If the complexity increases exponentially compared to the input size, it might be in the class O(n^2) for instance.

Recursion definitely can get tricky, but the idea is to "expand it out", specifically by setting up a recurrence relation. Here's a really good tutorial on using recurrence relationships to find the time complexity of recursive algorithms: http://www.cs.duke.edu/~ola/ap/recurrence.html