时间戳

首页 > 解决方案 > 计算处理组合javascript的时间

javascript - 计算处理组合javascript的时间

问题描述

我有这个功能：https ://rosettacode.org/wiki/Combinations#ES6

在我的环境console.log(show(comb(3,15)));中（与下面的这个片段相同）采取 aprox。4秒处理

如果我尝试console.log(show(comb(3,16))); 采取aprox。16 秒

如果我尝试console.log(show(comb(3,17))); 采取aprox。90 秒

但是如果我尝试过：console.log(show(comb(3,20))); 经过一小时的过程还没有完成，我已经停止了它。

问题是：

如何预先计算处理时间comb(3,50)或comb(3,80)？

(() => {
    'use strict';

 
    // COMBINATIONS -----------------------------------------------------------
 
    // comb :: Int -> Int -> [[Int]]
    const comb = (m, n) => combinations(m, enumFromTo(0, n - 1));
 
    // combinations :: Int -> [a] -> [[a]]
    const combinations = (k, xs) =>
        sort(filter(xs => k === xs.length, subsequences(xs)));
 
 
    // GENERIC FUNCTIONS -----------------------------------------------------
 
    // cons :: a -> [a] -> [a]
    const cons = (x, xs) => [x].concat(xs);
 
    // enumFromTo :: Int -> Int -> [Int]
    const enumFromTo = (m, n) =>
        Array.from({
            length: Math.floor(n - m) + 1
        }, (_, i) => m + i);
 
    // filter :: (a -> Bool) -> [a] -> [a]
    const filter = (f, xs) => xs.filter(f);
 
    // foldr (a -> b -> b) -> b -> [a] -> b
    const foldr = (f, a, xs) => xs.reduceRight(f, a);
 
    // isNull :: [a] -> Bool
    const isNull = xs => (xs instanceof Array) ? xs.length < 1 : undefined;
 
    // show :: a -> String
    const show = x => JSON.stringify(x) //, null, 2);
 
    // sort :: Ord a => [a] -> [a]
    const sort = xs => xs.sort();
 
    // stringChars :: String -> [Char]
    const stringChars = s => s.split('');
 
    // subsequences :: [a] -> [[a]]
    const subsequences = xs => {
 
        // nonEmptySubsequences :: [a] -> [[a]]
        const nonEmptySubsequences = xxs => {
            if (isNull(xxs)) return [];
            const [x, xs] = uncons(xxs);
            const f = (r, ys) => cons(ys, cons(cons(x, ys), r));
 
            return cons([x], foldr(f, [], nonEmptySubsequences(xs)));
        };
 
        return nonEmptySubsequences(
            (typeof xs === 'string' ? stringChars(xs) : xs)
        );
    };
 
    // uncons :: [a] -> Maybe (a, [a])
    const uncons = xs => xs.length ? [xs[0], xs.slice(1)] : undefined;
 
 
    // TEST -------------------------------------------------------------------
    // return show(
        // comb(3, 5)
    // );
    
    console.log(show(comb(3,15)));
})();

标签： javascript

解决方案

使用二项式系数。处理时间comb(3,n)是n choose 3，n*(n-1)*(n-2)/6因此是O(n^3)。例如，增加n10 倍应该会使运行时间增加大约 1000 倍。

20 choose 3只有 1140，所以如果生成它们需要一个多小时，那么所讨论的算法并不是特别好。此外，和之间的差距20 choose 3并17 choose 3没有太大，以至于它真正解释了时差。因此，渐近分析只是暗示正在发生的事情。实际的运行时间似乎更糟。

推荐阅读