행렬과 효율로 링크 된리스트

Question

알고리즘에서 큰 행렬을 사용해야 할 때, 복잡성을 줄이기 위해 행렬이 희소 한 경우 링크드리스트를 사용해야한다고 들었다. 데이터가 거의 같은 경우 해당 값이 아닌 데이터 만 저장할 수 있습니다.

그러나 스파 스 매트릭스를 사용하는 것이 더 이상 유용하지 않다는 점을 어떻게 식별 할 수 있습니까?

길이가 n 인 정사각형에 대해 행렬에 연결된 목록에 너무 많은 0이 아닌 데이터가 쓰여 있다고 말할 수있는 지점을 계산하는 방법은 무엇입니까?

우리는 객체의 메모리 크기, 두 객체 사이의 링크를 사용해야한다고 생각하고 밀도 인자를 사용합니다. 하지만 안전하게 계산할 수있는 것은 무엇입니까 "이 행렬에는 x %가 아닌 데이터가 있습니다. 연결된 목록을 사용하는 것이 더 좋습니다.?

Answer 1

귀하의 질문에 대한 답변은 최적화 대상에 달려 있습니다. 공간 또는 시간?

공간에 맞게 최적화한다고 가정 해 보겠습니다. 길이가 n 인 정사각형 행렬의 데이터를 유지하려면 n * n 개의 숫자가 필요합니다 (단순화하기 위해 각 값에 대한 정수라고 가정 해 봅시다). 연결된 목록을 만들려면 실제 값, 행렬 값의 좌표 및 다음 0이 아닌 값에 대한 포인터가 있어야합니다. 단순화하기 위해 각 필드의 크기가 정수인 경우 연결 목록 , 유지할 단일 값에 4 개의 정수가 필요합니다. 연결된 목록).

IMHO, 행렬 값의 1/4 미만이 0이 아닌 경우 배열 목록보다 연결된 목록을 사용하는 것이 더 적합합니다.

분명히 매트릭스 값을 유지하는 다른 옵션이 있습니다. 그 비율은 다를 수 있습니다.

다시 시간을 최적화하려면 실행하려는 작업에 따라 달라집니다.