V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
luoway
V2EX  ›  程序员

请问这个算法时间复杂度是否为 O(n!)

  •  
  •   luoway · 2015-10-11 16:18:18 +08:00 · 2644 次点击
    这是一个创建于 3322 天前的主题,其中的信息可能已经有所发展或是发生改变。
    对于字符串的所有字符组合,我设计了如下算法:
    eg."abc"

    abc
    ab, ac, bc
    a, b, c
    可见下层是上层每个结果去除一个字符,经过去重得到的结果。

    那么程序可以这样写

    递归函数名 (字符串){
    __保存字符串;
    __for 循环对字符串遍历{
    ____函数:删除该字符串中的某位置字符,返回新字符串____//此处被运算总计 n!次
    ____if 判断新字符串长度>1 则,
    ______递归函数(新字符串)
    ____否则,保存新字符串
    __}


    如注释,该算法的渐近时间复杂度即为 O(n!)
    9 条回复    2015-10-12 09:02:26 +08:00
    zzy8200
        1
    zzy8200  
       2015-10-11 17:20:27 +08:00 via iPhone
    为什么不用 2^n 算法?
    luoway
        2
    luoway  
    OP
       2015-10-11 17:24:58 +08:00
    @zzy8200 不会……
    zzy8200
        3
    zzy8200  
       2015-10-11 23:35:30 +08:00 via iPhone   ❤️ 1
    @luoway
    for i=1 to 2^n-1
    k=二进制(i)
    然后用 k 给字符串做 mask ,保留 1 的位
    输出
    done

    例: abc
    i=7 ( 111 )

    abc
    111

    ->abc

    i=6 (110)
    abc
    110

    ->ab
    luoway
        4
    luoway  
    OP
       2015-10-11 23:40:51 +08:00
    @zzy8200 这种情况下二进制确实好用!多谢指点!
    edfward
        5
    edfward  
       2015-10-12 00:45:02 +08:00   ❤️ 2
    题:[Subsets on LeetCode]( https://leetcode.com/problems/subsets/)
    解法:[Power Set - GeeksforGeeks]( http://www.geeksforgeeks.org/power-set/)
    luoway
        6
    luoway  
    OP
       2015-10-12 01:00:52 +08:00 via Android
    @edfward 没刷过题-_-||
    ryd994
        7
    ryd994  
       2015-10-12 04:54:46 +08:00 via Android   ❤️ 1
    其实不用二进制也行,还是递归
    你的问题主要是有重复解
    ab 去掉 b 和 ac 去掉 c 都是一样的
    可以反过来,递加
    a b c
    ab ac bc
    abc
    当考虑两个字母的解的时候,只考虑当前字母往后的。比如考虑 b 开头的解,就不需要考虑 ba ,因为 ab 肯定包含
    imcoddy
        8
    imcoddy  
       2015-10-12 07:46:14 +08:00
    @edfward 赞。其实这题的 Discuss 里面也有人提出了这个做法的。虽然我刷这题的只是弱弱地用了 Backtracking
    luoway
        9
    luoway  
    OP
       2015-10-12 09:02:26 +08:00 via Android
    @ryd994 正序考虑过,想的是在长度 4 以上的时候先求出含 a 的所有情况(长度 1,2,3),再求不含 a 的。比较复杂。于是倒序想到这个算法。
    现在使用每层长度只变 1 ,发现正序递加也能算。
    如 abcd
    a b c d
    ab ac ad bc bd cd
    abc abd acd bcd
    abcd
    没有重复,比递减更好。
    多谢指点!
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1930 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 28ms · UTC 16:27 · PVG 00:27 · LAX 08:27 · JFK 11:27
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.