0
그래서 그래프를 만드는 데 사용하는 이름 목록이 있습니다. 각 이름은 그래프의 노드이고 가장자리는 이름 사이의 최소 편집 거리로 가중치가 적용됩니다. 내 작업을 위해 각 이름 사이에 가중치를 만들어야합니다. for 루프를 구현하기 위해 중첩되어 있으며 내 프로그램이 그래프를 작성하는 데 오랜 시간이 걸립니다. 이 작업을 수행하는 더 빠른 방법이 있습니까?완전한 그래프를 더 빨리 만들 수 있습니까?
항상 모든 가장자리가 필요합니까? 느슨하게 만들 수 있습니다. 즉 처음으로 필요할 때만 가중치를 계산할 수 있습니다. – Henrik
음, 전체 그래프를 작성한 후에 임의의 노드에서 Prim의 MST 알고리즘을 실행한다고 가정합니다 ... –
@ user2079303은 아래에서 언급했듯이 가장자리를 작성하는 것은 O (n^2) 여야합니다 - 피할 수있는 방법이 없습니다 그. 그러나 아마도 "최소 편집 거리"기능이 제대로 작동하지 않습니다 ...? 사용중인 알고리즘에 따라 두 문자열의 길이에 지수 (순진한 재귀 알고리즘) 또는 O (백만)가 될 수 있습니다. 이름이 길면 빨리 추가 할 수 있습니다 ... – twalberg