我想了解我的程序的时间和空间复杂性

2024-03-29 08:59:28 发布

您现在位置:Python中文网/ 问答频道 /正文

import string
letters = string.ascii_lowercase
CHARACTER_HASH = dict(zip(letters, [0]*len(letters)))

def mapLettersToHash(text_a):
  for char in text_a:
    if char in CHARACTER_HASH.keys():
      CHARACTER_HASH[char]+=1

def computeCommonLetters(text_b):
  common_letters = 0    
  for char in text_b:
    if CHARACTER_HASH[char] > 0:
      common_letters+=1
  return common_letters

def computeUncommonLetters(text_a, text_b, common_letters):
  return len(text_a)+len(text_b)-(2*common_letters)

text_1 = "hello"
text_2 = "billion"

mapLettersToHash(text_1)
common = computeCommonLetters(text_2)
result = computeUncommonLetters(text_1, text_2, common)
print(result)    

问题:给定两个大小为m和n的字符串,我们必须找出需要从这两个字符串中删除多少字符,以便它们成为彼此的anagram

我试图计算我的程序的空间和时间复杂性。 根据我的扣除:

  1. 创建字符哈希需要固定的时间和空间

  2. 接下来,映射文本的字符(如果大小是m)将花费O(m)时间

  3. 接下来,从文本b(如果大小为n)计算公共字符将花费O(n)时间

  4. 计算不常见字符是一个简单的算术运算,因此需要固定的时间。

因此,我的最终课程将有:

时间复杂度:O(m+n)

空间复杂度:O(1){由于字符散列}

如果我错过了什么,请告诉我?谢谢


Tags: textinforstringlendef时间空间