목록 작성의 공간 복잡도

Question

누군가가 프로그램 너머의 공간 복잡성이 무엇인지 설명 할 수 있습니까? 그 이유는 무엇입니까?

def is_pal_per(str): 

s = [i for i in str] 
nums = [0] * 129 

for i in s: 
    nums[ord(i)] += 1 

count = 0 

for i in nums: 
    if i != 0 and i/2 == 0: 
     count += 1 

print count 

if count > 1: 
    return False 
else: 
    return True 

사실 나는이 코드 라인에 흥미가 있습니다. 위의 프로그램의 공간 복잡성에 어떻게 영향을 줍니까?

s = [i for i in str] 
nums = [0] * 129 

첫 번째는 상수이며, 선형 적으로 증가 len(str) :

s = [i for i in str] 

nums = [0] * 129

Answer 1

어디에서 문제가 있는지 잘 모르겠습니다. s은 단순히 str의 개별 문자 목록입니다. 공간 소비량은 len (s)입니다.

nums은 O (N) 용어가 지배적 인 고정 크기입니다.

이 코드는 작성 했습니까? 프로그래밍 스타일은 이 아니며 "Pythonic"이 아닙니다.

---

코드에 관해서는,이 붕괴 시작 :; 내가 =>발

count = 0 

for char in str: 
    val = ord[char] + 1 
    if abs(val) == 1: 
     count += 1 

print count 

return count == 0 

첫째, 나는 당신의 단일 문자 변수 (의 =>문자 교체). 그런 다음 중간 단계의 을 대부분으로 잘라내어 코드를 읽는 데 도움이됩니다. 마지막으로, 나는 원래의 복잡한 말 대신에 반환하는 간단한 부울 값을 사용했습니다.

나는 이 아닙니다.은 파이썬의 계산 방법을 사용합니다. 이것은 함수를 훨씬 더 단축시킵니다. 그런데 에이 있습니다. 단위 값의 수를 출력합니까, 아니면 부울 반환 만 필요합니까? 반환 값이라면 더 짧게 만들 수 있습니다.

Answer 2

하면 메모리를 할당 단 두 줄을 발견 하였다. 따라서 함수의 공간 복잡도는 O (N)이고 N = 길이는 str입니다.