标签: time-complexity

给定[0..n ^ 3-1]范围内的n个整数的输入集,提供线性时间排序算法.

这是我星期四测试的评论,我不知道如何解决这个问题.

嵌套的 for、while 和 if 语句的时间复杂度相同吗？假设a是一个长度为 的数组n。

for _ in range(len(a)):\n    for _ in range(len(a)):\n        do_something\n

上面的 for 语句的复杂度为 O(n\xc2\xb2)。

i = 0\nwhile i < len(a) * len(a):\n    do_something\n    i += 1\n

乍一看，上面的循环可以认为是 O(n)，但最终我认为也是 O(n\xc2\xb2)。

我对吗？

使用动态编程可以解决许多问题,例如最长的增加子序列.这个问题可以通过使用2种方法来解决

1. Memoization(自上而下) - 使用递归来解决子问题并将结果存储在某个哈希表中.
2. 制表(自下而上) - 使用迭代方法通过首先解决较小的子问题然后在执行更大的问题期间使用它来解决问题.

我的问题是哪种方法在时间和空间复杂性方面更好？

如何计算这些回溯算法的时间复杂度,它们是否具有相同的时间复杂度？如果不同怎么样？请详细解释并感谢您的帮助.

1. Hamiltonian cycle:

        bool hamCycleUtil(bool graph[V][V], int path[], int pos) {
            /* base case: If all vertices are included in Hamiltonian Cycle */
            if (pos == V) {
                // And if there is an edge from the last included vertex to the
                // first vertex
                if ( graph[ path[pos-1] ][ path[0] ] == 1 )
                    return true;
                else
                    return false;
            }

            // Try different vertices as a next candidate in Hamiltonian Cycle.
            // We don't try for 0 as …

有许多现实世界的问题,结果证明是NP- hard.如果我们假设P ≠ NP,则对于这些问题没有任何多项式时间算法.

如果您必须解决其中一个问题,您是否有希望能够有效地解决这些问题？或者你只是运气不好？

我很好奇,首先,为什么std::list并将std::forward_list排序函数作为成员函数包含在内,与其他标准库容器不同.但对我来说更有趣的是,CPPReference和CPlusPlus都声称这种排序是在O(n log n)时间内完成的.

我甚至无法想象如何在没有随机访问元素的情况下对容器进行排序.所以我把测试组合起来,forward_list尽可能地使它变得困难.

#include <chrono>
#include <cstdint>
#include <deque>
#include <forward_list>
#include <iostream>
#include <random>

using std::endl;
using namespace std::chrono;

typedef nanoseconds::rep length_of_time;
constexpr int TEST_SIZE = 25000;


class Stopwatch
{
    public:
        void start_timing();
        void end_timing();
        length_of_time get_elapsed_time() const;
    private:
        time_point<high_resolution_clock> start;
        time_point<high_resolution_clock> end;
        length_of_time elapsed_time = 0;
};


void Stopwatch::start_timing()
{
    start = high_resolution_clock::now();
}


void Stopwatch::end_timing()
{
    end = high_resolution_clock::now();
    auto elapsed = end - …

切片Python字符串的时间复杂度是多少？鉴于Python字符串是不可变的,我可以想象将它们切片为O(1)或者O(n)取决于切片的实现方式.

我需要编写一个迭代一个(可能很大)字符串的所有后缀的函数.我可以通过将后缀表示为整个字符串的元组加上一个开始读取字符的索引来避免切片,但这很难看.如果相反,我天真地写这样的函数:

def do_something_on_all_suffixes(big_string):
    for i in range(len(big_string)):
        suffix = big_string[i:]
        some_constant_time_operation(suffix)

... ...将其时间复杂度是O(n)或,其中是？O(n2)nlen(big_string)

什么是创建一个复杂线索单词列表的,什么是该线索寻找另一组字的复杂性？当我有哈希表时,我应该使用trie进行字符串搜索吗？

所以我可以想象一个算法是什么,它具有n ^ c的复杂性,只是嵌套for循环的数量.

for (var i = 0; i < dataset.len; i++ {
    for (var j = 0; j < dataset.len; j++) {
        //do stuff with i and j
    }
}

Log是每次将数据集分成两半的东西,二进制搜索就是这样(不完全确定这个代码是什么样的).

但是什么是c ^ n或更具体地2 ^ n的算法的简单示例.O(2 ^ n)是基于数据循环吗？或者如何拆分数据？或完全不同的东西？

Google编程面试中提到了这个问题.我想到了两种相同的方法:

1. 找到所有长度的子序列.这样做的同时计算两个元素的和,并检查它是否等于k.如果是的话,打印是,否则继续搜索.这是一种蛮力的方法.

2. 以非递减顺序对数组进行排序.然后从右端开始遍历数组.假设我们有排序数组{3,5,7,10},我们希望总和为17.我们将从元素10开始,索引= 3,让我们用'j'表示索引.然后包括当前元素并计算required_sum = sum - current_element.之后,我们可以在数组[0-(j-1)]中执行二进制或三进制搜索,以查找是否存在其值等于required_sum的元素.如果我们找到这样一个元素,我们可以打破,因为我们找到了长度为2的子序列,其总和是给定的总和.如果我们没有找到任何这样的元素,那么减小j的索引并重复上述步骤以得到长度=长度为1的子阵列,即在这种情况下通过排除索引3处的元素.

在这里,我们认为数组可能有负整数和正整数.

你能提出比这更好的解决方案吗？DP解决方案可能吗？一种可以进一步降低时间复杂度的解决方案.