2 
private void listAll( int depth )
{
    printName( depth ); // Print the name of the object
    if( isDirectory( ) )
    for each file c in this directory (for each child)
    c.listAll( depth + 1 );
}

我尝试使用递归关系来诱导运行时间
正确的运行时间是 O(N)
我的分析表明它将是 O(N^2)

这是我的归纳
1. T(0) = (第一行) O(1)+(第二行) O(1)+(我们假设的孩子数是 N) N*(T(1)
2. T(0 ) = (第一行) O(1)+(第二行) O(1)+ N*(O(1)+O(1)+ N*(T(2))
3 随着这个归纳的进行，运行时间将是某种 O(N^2)

我的分析有什么问题？？？

4

3 回答 3

4

你的错误在于假设有 N 个孩子。如果 N 是文件总数，您应该观察 O(N) 运行时。

于 2013-03-14T20:01:17.253 回答
0

您可能误解了 N 的含义？也许 N 是根目录及其所有子目录中所有文件的数量，这会使这个问题成为深度优先搜索，它具有 O(N) 复杂度，其中 N 是节点数。

如果确实是 N^2，那么一个目录中的文件数和另一个目录中的文件数必须具有某种依赖性。但事实并非如此......每个文件夹中的文件数量是未定义的，除非您实际访问它。可以是2，也可以是一万。

于 2013-03-14T20:03:15.853 回答
0

如果单步是指一次调用，listAll()并且N是目录结构中的元素总数，则必须是一次调用listAll()必须对应于单个元素，否则您将多次打印至少一个元素。

因此，您得到O(N)（实际上，正好是 N * recursive_call_cost）

于 2013-03-14T20:03:58.263 回答