5
이것은 답을 표현하는 데 문제가있는 할당 질문입니다.트리 : 연결된 목록 대 배열 (효율성)
"노드 당 최대 k 개의 자식을 가질 수 있다고 가정 할 때 노드 당 평균 자식 수를 v라고 가정 할 때 v를 저장하는 데 사용 된 v의 값은 무엇입니까? 링크 된 목록의 자식 노드 대 배열의 저장소? 왜? "
나는 "왜?"라고 대답 할 수 있다고 생각합니다. 보통 영어로 더 많거나 적음 - 링크 된 목록을 사용하는 것이 더 효율적입니다. 빈 노드 (즉, 평균이 최대보다 작은 경우 배열의 빈 인덱스)를 사용하는 것보다 공간을 할당하는 것보다 메모리를 많이 사용하기 때문입니다 실제로 값을 채울 때 링크 된 목록의 노드에 대해.
최대 200 개일 때 평균 6 명의 자녀가있는 경우 트리는 트리를 만들 때 각 노드의 모든 200 명의 자녀를위한 공간을 생성하지만 링크 된 목록은 필요에 따라 노드. 따라서 연결된 목록에서 사용 된 공간은 평균 (?)입니다. 배열과 함께 사용되는 간격은 최대 값이됩니다.
... 배열을 사용하는 것이 더 효율적일 때 나는 볼 수 없습니다. 이게 속임수입니까? 배열을 만들 때 총 노드 수에 배열에 제한이 있어야한다는 사실을 고려해야합니까?
연결 목록의 오버 헤드가 무슨 뜻인지 잘 모르겠습니다. 레퍼런스에 필요한 메모리에 대해 이야기하고 있습니까? –
@dc : 링크드리스트는 어떻게 구현 되나요? 얼마만큼의 메모리가 필요합니까? –