통신 복잡성

Question

문자열을 서버로 보내고 복잡성을 계산하려고합니다.

각 문자열 ss의 모든 안내문을 보내고 있습니다. 따라서 한 문자를 입력 한 다음 두 문자를 입력하고 세 문자를 입력하여 문자를 보내십시오. |s| 자까지 문자를 보내십시오.

여기서 의사 소통의 복잡성은 무엇입니까? 나는 O(|s|²)를 말했을 것이지만 나는 확실하지 않다.

또 다른 알고리즘에서 나는 s의 각 문자에 대해 고정 크기의 데이터를 보내고 있습니다 (100 문자로 가정). 그래서 |s| * 100 문자를 보내고 있습니다. 이제 이건 O(|s|)에 있어야합니까? 그러나 어느 것이 더 나빠요? 분명히 짧은 s에 대한 첫 번째 알고리즘이 더 낫지 않습니까, 아니면 여기서 완전히 떨어져 있습니까?

Answer 1

내가 틀렸다면 나를 수정하십시오.

한 문자를 전송 한 다음 두 문자를 입력 한 다음 세 ... 최대 보내기 보내는 중 | 문자.

첫 번째 문자를 보낼 때 남은 문자 (| S | -1)가 있거나 매번 다시 시작하는 중입니다. | S | 첫 번째 가능성을

• :

가의 그런 말을하자 | S | = N

1 + 2 + ... + n은 N (N-1)/2

(| S |^2) O 번째 가능성

• :이 경우

  복잡하다 1 + 2 + ... + A = | S |

이 경우 복잡성은 다음과 같습니다 O (| S |)

선형 시간 복잡도가 더 나은 모든 시간을, 자세한 내용은이 튜토리얼을 확인할 수있는 요인을 나타내는 c는 약 complexity time

Answer 2

하자 두 번째 알고리즘에서 귀하의 예에서는 c를 100으로 설정합니다. 그런 다음 두 번째 알고리즘에는 c * | s |가 필요합니다. 전송할 문자. user3378649가 지적했듯이, 첫 번째 알고리즘은 | s | * (| s | -1)/2 문자를 전송해야합니다.

이제는 c * | s |가있을 때마다 동일한 비용을 갖는 것을 쉽게 알 수 있습니다. = | S | * (| S | -1)보다 간결/2 이상 :

C = (| S | -1)/2

물론, 경우 C < (| S | -1)/2이면 두 번째 알고리즘의 비용은 더 적으며 c> (| s | -1)/2 인 경우 첫 번째 알고리즘의 비용은 낮아집니다. | S |

1. 전형적인 가치는 무엇입니다 :
   는 실질적인 문제로이 아이디어를 생각해야했다 가졌?불평등 중 하나가 항상 충족된다는 보장이 있다면 (예 : < 10을 보장 할 수있는 경우) 적절한 알고리즘을 선택해야합니다.
2. 시스템이 얼마나 오래 지연 될 수 있습니까? 일관되게 첫 번째 알고리즘을 사용하면 비정상적으로 큰 문자열이 생길 때 문제가 발생할 수 있습니다. 99 %의 데이터가 실제로 짧은 경우에도 긴 지연으로 인한 잠재적 인 사용자 영향이 문제가 될 수 있습니다.
3. 알고리즘을 모두 알고리즘으로 사용할 수 있습니다. | s | | 작을 때 두 번째 알고리즘을 사용합니다. 크다.
4. 전체 문자열을 적당한 크기의 덩어리로 보내는 것으로 생각하고 커뮤니케이션의 다른 쪽을 접두어 밖으로 내 보내려 했습니까? 데이터 전송은 일반적으로 계산 시간보다 비쌉니다. 또한 통신 개시 비용도 고려해야합니다. 통신 전송은 일반적으로 최소 블록 크기를 사용하므로 작은 메시지를 분리하는 것은 권장되지 않습니다.

행운을 빌어 요!