标签: space-complexity

当谈到算法的空间复杂度时，我感到很困惑。理论上，它对应于算法使用的额外堆栈空间，即输入以外的空间。然而，我很难指出这到底是什么意思。

例如，如果我有一个以下的强力算法来检查数组中是否没有重复项，这是否意味着它使用 O(1) 额外的存储空间，因为它使用 int j 和 int k？

 public static void distinctBruteForce(int[] myArray) {
    for (int j = 0; j < myArray.length; j++) {
        for (int k = j + 1; k < myArray.length; k++) {
            if (k != j && myArray[k] == myArray[j]) {
                return;
            }
        }
    }
}

我写了一段两和的代码：

public static int[] twoSums0(int[] nums, int target){

    for(int i=0;i<nums.length;i++){
        for(int j=i+1;j<nums.length;j++){
            if(nums[i] == target-nums[j]){
                return new int[]{i,j};
            }
        }
    }
    throw new IllegalArgumentException("No solution");
}

我只想知道，为什么空间复杂度是O(1)？为什么当我们使用 hashmap 时，它会变成 O(n) ？

时间复杂度很容易理解，但我不明白空间复杂度。

我在编码面试中遇到了这个问题：

# AAABB should return A3B2

这是一道经典的算法面试题。我说我可以在O(n)时间和O(1)空间上解决这个问题。

def compress(s):

    output = ''
    count = 1

    for i in range(len(s)-1):
        if s[i] == s[i+1]:
            count+=1
        else:
            output = output + s[i] + str(count)
            count=1

    output = output +s[i+1] + str(count)
    return output

compress('AAABB') #returns A3B2

我理解O(n)空间意味着它随着输入的大小成比例地增长。所以我想O(n)空间看起来会是这样的 [(A,3),(B,2)]。

我的印象A3B2是在O(1)太空中，因为它没有被分成多个字符串。

我现在意识到，n == len(s)我的输出与我的输入大小不成比例（更少）地增长，所以说空间是正确的吗O(log n)？

我试图了解图中 DFS 和 BFS 的空间复杂度是多少。据我所知，使用邻接矩阵时 BFS 的空间复杂度是O(v^2)顶点v​​数。

通过使用邻接表，在平均情况下，空间复杂度将会降低< v^2。但在最坏的情况下，情况会是这样O(v^2)。即使包括队列，它也会O(n^2)（忽略较低的值）

但是，DFS 的场景是什么？即使我们使用邻接矩阵/列表。空间复杂度为 O(v^2)。但这似乎是一个非常宽松的界限，也不考虑堆栈帧。

关于复杂性，我的说法正确吗？如果，不是，BFS/DFS 的空间复杂度是多少？在计算DFS的空间复杂度时，我们是否考虑堆栈帧？

图的 BFS 和 DFS 的空间复杂度的紧界是多少

这是破解编码面试5问题9.4^次
的问题：写返回一组的所有子集的方法。

这是我在 Java 中的解决方案。（测试它，它有效！！！）

public static List<Set<Integer>> subsets(Set<Integer> s) {
    Queue<Integer> copyToProtectData  = new LinkedList<Integer>();
    for(int member: s) {
        copyToProtectData.add(member);
    }
    List<Set<Integer>> subsets = new ArrayList<Set<Integer>>();
    generateSubsets(copyToProtectData, subsets, new HashSet<Integer>());
    return subsets;
}
private static void generateSubsets(Queue<Integer> s, 
        List<Set<Integer>> subsets, Set<Integer> hashSet) {
    if(s.isEmpty()) {
        subsets.add(hashSet);
    } else {
        int member = s.remove();
        Set<Integer> copy = new HashSet<Integer>();
        for(int i:hashSet) {
            copy.add(i);
        }
        hashSet.add(member);
        Queue<Integer> queueCopy = new LinkedList<Integer>();
        for(int i:s){
            queueCopy.add(i);
        }
        generateSubsets(s, subsets, hashSet);
        generateSubsets(queueCopy, …

我有两段代码如下:

code 1:

Optional.fromNullable(integerVsLongMap.get(id)).or(getDefaultLong());

和

code 2:

integerVsLongMap.contains(id) ? integerVsLongMap.get(id) : getDefaultLong();

我想知道哪一段代码在空间和时间复杂度以及编码实践方面更有效率和更优选,因为我看到的是两者都做同样的事情？

如果我使用以下代码从字符串S中删除空格,是否会将其视为使用额外的空格/内存？给出'S'字符串'l'长度.

int n = l
while i < n
    if S[i] == " ":
        S = S[0:i] + S[i+1:]
    n = len(S)
print "the new string ", S

编辑:这只是一个示例代码.请不要评论它的复杂性和/或删除空格的正确方法:).这里的上下文是,在解决算法设计问题时,涉及一些字符串操作,使用额外空间的限制.我想知道这样的操作是否使用额外的内存/空间.

In python3 range built with help of generators

对数时间— O（log n）当算法在每一步中减少输入数据的大小时，被称为具有对数时间复杂度。例如，如果我们要在生成器的帮助下打印前10位数字，则首先将得到一个元素，因此剩下的9个元素必须处理，然后再得到第二个元素，因此剩下的8个元素必须处理

for index in range(0, len(data)):
    print(data[index])

当我检查python生成器的时间复杂度时，它说O（n）。

由于每次它只生成一个输出（因为我们需要这样做），__next__ 因此每次将生成1个单位成本。

我可以对此进行解释吗

哪种方法更快？他们不是一样吗？

start = time.time()
arr = np.array([1,2,3,4,5,6,7,8,9,0,12])
total_price =  np.sum(arr[arr < 7])* 2.14

print(total_price)
print('Duration: {} seconds'.format(time.time() - start))

start = time.time()
arr = np.array([1,2,3,4,5,6,7,8,9,0,12])
total_price =  (arr[arr<7]).sum()* 2.14

print(total_price)
print('Duration: {} seconds'.format(time.time() - start))

一次又一次地运行代码时，它们都会给出不同的最终执行时间。有时前一种方法更快，有时更晚。

void recursiveInsertionSort(vector<int> &arr, int n) {
    if (n <= 1)
        return;
    recursiveInsertionSort(arr, n - 1);
    int val = arr[n - 1], j = n - 2;
    for (j = n - 2; j >= 0 && arr[j] > val; --j)
        arr[j + 1] = arr[j];
    arr[j + 1] = val;
}

我认为空间复杂度是常数（O(1)），因为我通过引用传递数组。

但我被告知它实际上是 O(n)。这是为什么 ？

我想为这个问题编写代码:

给定一个字符串,在O(n)时间和O(1)空间中删除它的重复项.

现在,我编写了一个代码来删除字符串中的重复项.

public class RemoveDuplicates
{
    public static void main(String args[])
    {
        String input = "aabbccc";
        char[] inputArray = input.toCharArray();
        for(int i=0;i<inputArray.length;i++)
        {
            for(int j=i+1;j<inputArray.length;j++)
            {
                if(inputArray[i] == inputArray[j])
                    inputArray[j] = ' ';
            }
        }
        input = new String(inputArray);
        input = input.replaceAll("\\s+","");
        System.out.println("The String after removing duplicates is : "+input);
    }
}

实际上,我正在拍摄一个角色并与其他人进行比较,如果发现它们相等,则用空格替换找到的角色.最后,删除字符串中的所有空格.

我有一个基本的理解,它必须是O(n ^ 2)实现(关于时间)因为使用两个for循环.如何修改我的代码的O(n)时间和O(1)空间复杂度？

或者换句话说,O(1)空间要求意味着什么？我应该在时间要求中使用单个for循环而不是两个吗？