两种递归方法的Java复杂度-6ren

两种递归方法的Java复杂度

转载作者：搜寻专家更新时间：2023-11-01 02:07:15

25

4

public static String rec1 (String s) {

    int n = s.length()/2; 
    return n==0 ? s : rec1(s.substring(n)) + rec1(s.substring(0,n)); 
}


public static String rec2 (String s) {
    return s.length()<=1 ? s : rec2(s.substring(1)) + s.charAt(0); 
}

为什么rec2的复杂度大于rec1？

我对每个迭代都进行了 10.000 次迭代，并使用 System.nanoTime() 测量了执行时间，结果如下:

rec1: Stringlength: 200  Avgtime: 19912ns Recursive calls: 399rec1: Stringlength: 400  Avgtime: 42294 ns Recursive calls: 799rec1: Stringlength: 800  Avgtime: 77674 ns Recursive calls: 1599rec1: Stringlength: 1600 Avgtime: 146305 ns Recursive calls: 3199rec2: Stringlength: 200  Avgtime: 26386 ns Recursive calls: 200rec2: Stringlength: 400  Avgtime: 100677 ns Recursive calls: 400rec2: Stringlength: 800  Avgtime: 394448 ns Recursive calls: 800rec2: Stringlength: 1600 Avgtime: 1505853 ns Recursive calls: 1600

所以当字符串长度为 1600 时，rec1 比 rec2 快 10 倍。我正在寻找一个简短的解释。

enter image description here

最佳答案

根据 Time complexity of Java's substring() ，String#substring 现在复制支持数组，O(n) 时间复杂度也是如此。

利用这个事实可以看出 rec1 具有时间复杂度 O(n log n) 而 rec2 具有时间复杂度 O(n^2) 。

从初始 String s = "12345678" 开始。为简单起见，我将长度取为 2 的幂。

rec1 :

s 分为 "1234" 和 "5678" 。
这些分为 "12" , "34" , "56" , "78"
这些分为 "1" 、 "2" 、 "3" 、 "4" 、 "5" 、 "6" 、 "7" 、 "8"

这里有 3 个步骤，因为 log(8) = 3 。每个 char 在每一步都被复制，所以复制的字符总数是 O(n log n) 。当 String 以相反的顺序重新组装时，上面的 Strings 现在使用连接连接在一起，使用以下步骤:

字符串被连接成 "21" , "43" , "65" , "87"
字符串连接成 "4321" , "8765"
连接字符串以生成 "87654321" 。

这又是一共O(n log n)复制的字符!

rec2 :

s 分为 "1" 和 "2345678" 。
"2345678" 分为 "2" 和 "345678" 。
"345678" 分为 "3" 和 "45678" 。
"45678" 分为 "4" 和 "5678" 。
"5678" 分为 "5" 和 "678" 。
"678" 分为 "6" 和 "78" 。
"78" 分为 "7" 和 "8" 。

这是 8 + 7 + 6 + 5 + 4 + 3 + 2 = 35 复制字符的总数。如果你懂代数，这将是 (n * (n+1)) / 2 - 1 复制的一般字符，所以 O(n^2) 。

当这一切逆序拼装后，复制字符数又会是O(n^2)。

关于两种递归方法的Java复杂度，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/29288677/

25

4

0

文章推荐： java - 如何替换java中的花括号？

文章推荐： javascript - onbeforeunload 的可靠性

文章推荐： javascript - 为什么慢速 jQuery 动画断断续续？

文章推荐： java - 如何在Java中获取两个日期之间的季度数

Ruby 方法() 方法
我想了解 Ruby 方法 methods() 是如何工作的。我尝试使用“ruby 方法”在 Google 上搜索，但这不是我需要的。我也看过 ruby-doc.org，但我没有找到这种方法。
VBS教程：方法-Test 方法
Test 方法对指定的字符串执行一个正则表达式搜索，并返回一个 Boolean 值指示是否找到匹配的模式。 object.Test(string) 参数 object 必选项。总是一个
VBS教程：方法-Replace 方法
Replace 方法替换在正则表达式查找中找到的文本。 object.Replace(string1, string2) 参数 object 必选项。总是一个 RegExp 对象的名称。
VBS教程：方法-Raise 方法
Raise 方法生成运行时错误 object.Raise(number, source, description, helpfile, helpcontext) 参数 object 应为
VBS教程：方法-Execute 方法
Execute 方法对指定的字符串执行正则表达式搜索。 object.Execute(string) 参数 object 必选项。总是一个 RegExp 对象的名称。 string
VBS教程：方法-Clear 方法
Clear 方法清除 Err 对象的所有属性设置。 object.Clear object 应为 Err 对象的名称。说明在错误处理后，使用 Clear 显式地清除 Err 对象。此
VBS教程：方法-CopyFile 方法
CopyFile 方法将一个或多个文件从某位置复制到另一位置。 object.CopyFile source, destination[, overwrite] 参数 object 必选
VBS教程：方法-Copy 方法
Copy 方法将指定的文件或文件夹从某位置复制到另一位置。 object.Copy destination[, overwrite] 参数 object 必选项。应为 File 或 F
VBS教程：方法-Close 方法
Close 方法关闭打开的 TextStream 文件。 object.Close object 应为 TextStream 对象的名称。说明下面例子举例说明如何使用 Close 方
VBS教程：方法-BuildPath 方法
BuildPath 方法向现有路径后添加名称。 object.BuildPath(path, name) 参数 object 必选项。应为 FileSystemObject 对象的名称
VBS教程：方法-GetFolder 方法
GetFolder 方法返回与指定的路径中某文件夹相应的 Folder 对象。 object.GetFolder(folderspec) 参数 object 必选项。应为 FileSy
VBS教程：方法-GetFileName 方法
GetFileName 方法返回指定路径（不是指定驱动器路径部分）的最后一个文件或文件夹。 object.GetFileName(pathspec) 参数 object 必选项。应为
VBS教程：方法-GetFile 方法
GetFile 方法返回与指定路径中某文件相应的 File 对象。 object.GetFile(filespec) 参数 object 必选项。应为 FileSystemObject
VBS教程：方法-GetExtensionName 方法
GetExtensionName 方法返回字符串，该字符串包含路径最后一个组成部分的扩展名。 object.GetExtensionName(path) 参数 object 必选项。应
VBS教程：方法-GetDriveName 方法
GetDriveName 方法返回包含指定路径中驱动器名的字符串。 object.GetDriveName(path) 参数 object 必选项。应为 FileSystemObjec
VBS教程：方法-GetDrive 方法
GetDrive 方法返回与指定的路径中驱动器相对应的 Drive 对象。 object.GetDrive drivespec 参数 object 必选项。应为 FileSystemO
VBS教程：方法-GetBaseName 方法
GetBaseName 方法返回字符串，其中包含文件的基本名 (不带扩展名), 或者提供的路径说明中的文件夹。 object.GetBaseName(path) 参数 object 必
VBS教程：方法-GetAbsolutePathName 方法
GetAbsolutePathName 方法从提供的指定路径中返回完整且含义明确的路径。 object.GetAbsolutePathName(pathspec) 参数 object
VBS教程：方法-FolderExists 方法
FolderExists 方法如果指定的文件夹存在，则返回 True；否则返回 False。 object.FolderExists(folderspec) 参数 object 必选项
VBS教程：方法-FileExists 方法
FileExists 方法如果指定的文件存在返回 True；否则返回 False。 object.FileExists(filespec) 参数 object 必选项。应为 FileS

首页

博学

6Ren·AI

商城

两种递归方法的Java复杂度