Notation Oh-big and complexity of social interactions
If you had to sit at an unbearably boring meeting where two people discuss a problem, and the rest are spectators, you are ready to accept the idea that this way of interaction is not effective. You may also have thought about alternatives. The mistake of the organizers of the meeting was that they chose the form of interaction that did not correspond to the task, and, thus, doomed a large number of people to waste time.
Some time ago, I realized that the assessment of the complexity of social interactions, you can apply the same approaches as for the assessment of the complexity of algorithms - which means you can see their pros, cons and areas of application. Below is a brief list of the most frequent options with which I dealt.
O (n 2 ): Meeting of equal participants. n people discuss the issue, and to achieve mutual understanding, each participant needs to communicate with everyone. In total, there will be n * (n-1) / 2 social interactions (equivalent to the task of counting the number of handshakes in a group of n people), that is, the complexity of the O (n 2 ) algorithm. It would seem that due to the fact that n / 2 pairs of people can simultaneously communicate, the time estimate is O (n) , but at real meetings only one person speaks at a time, therefore the worst case assessment is O (n 2 ) . If the interaction time is 5 minutes and it takes two iterations to reach full understanding in the group, then the meeting of three people will last 30 minutes, four hours, five will take 1 hour and 40 minutes to find a common solution (which is suspiciously like the truth). If the number of iterations depends on the number of participants, we get even more sad assessments.
')
But it is not all that bad!
- First, not all participants of the meeting can be independent and equal, they can form groups of interests (for example, the head and his two subordinates), then the discussion takes place not between individual participants, but between groups, of which there is always one person. A representative may change during the discussion, but he is always the only one. In this case, the complexity of social interaction is O ((n / m) 2 ) , where m is the average number of participants in each group present at the meeting.
- Secondly, O (n 2 ) is the worst estimate. It may turn out that each side expresses its position in turn, and each next one builds his statement taking into account everything he heard earlier. The last participant offers a solution to the problem - and all participants in the discussion agree with him or make their own minor changes. In this case, only 2n actions are enough to make a decision. Moral: a prepared presentation and a moderator defining the order of discussion can save a lot of time.
About (n * log (n)): working out a team decision through delegates. Often, making a decision requires a lot of people to be involved. The solution may cover a technically complex area or may require the efforts of a large number of people to implement. After the task is set, each of the participants offers a solution to their part of the task, setting it out to the delegate (for example, the head of his department). The delegate summarizes the received proposals and presents them to the delegate of the second level (selected among the delegates of the first level), who, in turn, summarizes the received proposals and presents them to the delegate of the third level - and so on. Continuing the algorithm recursively and reaching the person making the final decision, we will get an option that, to one degree or another, will take into account the opinion of each of the participants. And we get it quickly enough - due to the fact that communication with the delegate is perfectly parallel, we get the answer for O (m * log m (n)) , where m is the characteristic number of people in the group.
O (n): chain matching. Often the solution is already there, you just need to go through a standardized procedure for its approval. For example - to coordinate the addition of a new product on the shelf. Here, the complexity of one attempt will be equal to n , where n is the number of instances that will need to pass. Yes, the number of attempts is not limited in any way, but because requirements are known in advance, it is usually small.
About (n): alert. Ideal for situations where you need to bring some information unchanged to a large number of people. Each of the group will spend time on familiarization, so the effort will amount to n social interactions. In bad cases, the method may take the form "I ask you to familiarize yourself with the order and accept for execution", in good cases it is just a check for the correctness of the data, written in the code. The differences between these cases are in the number of people who actually encounter an alert (in the second, significantly less), as well as differences in the artist’s memory requirements (in the second, there’s no need to remember anything until the restriction works). But, personally, I like in this approach that it is O (1) in time for the sender - the labor costs will remain unchanged regardless of the number of people who receive the message. The dark side of the same rule - letters with dozens of people in a copy.
About (log (n)): notification through delegates. It is used when it is necessary to notify only one person, but it is not known who exactly. An example is a task that descends to management, then is transferred to the head of the department, then to the direct executor. An alternative way is to create a “single window” through which all tasks / orders / wishes are accepted. This way of setting the task is still constant in complexity for the sender, but much less labor-intensive for the receiving party, therefore it is the receiving party who, as a rule, initiates the change of the exchange method from “alert” to “alert via delegates”.
About (1): problem solving through a standard interface. The ideal situation to which, in my opinion, we must strive. The problem is known, as is the way to solve it, which means you can create an interface that will help a person solve his problem without any contact with other people, and the speed of solving the problem does not depend on the number of people who have encountered it. It can be said that this is the same “alert”, but from the point of view of the sender, and the real costs on the part of the users are still O (n) . This is true, but I decided to isolate this method, because, despite the mathematical equivalence, it gives a new look at the problem.
Are there ways of interacting with the outside world with complexity worse than O (n 2 ) ? Definitely yes - by analogy with the bog sorting you can come up with options that would be terribly impractical. I believe that they do not occur in practice just because all real problems are solved by less time-consuming algorithms.
If there are approaches in which the problem is solved in a constant time - then why do we need all the other methods? I believe that the main reason is freedom of decision making. Along with the improvement of the asymptotics, freedom gradually disappears. In a meeting of equal participants, the range of decisions is limited only to the powers of the people participating in the meeting. This tool is well suited for making important unique decisions. When using standard interfaces, the range of solutions is significantly narrowed.
Practical implications:
- Do not call to meetings of equal participants more than 5 people. If the time of one interaction between people is 5 minutes, most likely, you will not meet the 1 hour of discussion.
- do not call more than 15 people to meetings of unequal participants (5 heads + 2 subordinates from each side) - one hour is not enough for you again
-do not call to meetings people who only need “ok” - write a protocol on the results of the meeting and ask him to agree
- orders, instructions, informational messages (and, possibly, subsequent votes) is the only effective way to communicate if there are more than a few dozen stakeholders.
- if the department has more than 10 people - create a “single window” where standard requirements / wishes / requests will be received.
- if you or your employees do not have time to perform the tasks that come to them - think about whether you can improve the asymptotics by changing the way you interact with the outside world.
Ps Unfortunately, the speed of interaction between people does not double every two years.
Optimize your communication and be happy.
Some time ago, I realized that the assessment of the complexity of social interactions, you can apply the same approaches as for the assessment of the complexity of algorithms - which means you can see their pros, cons and areas of application. Below is a brief list of the most frequent options with which I dealt.
O (n 2 ): Meeting of equal participants. n people discuss the issue, and to achieve mutual understanding, each participant needs to communicate with everyone. In total, there will be n * (n-1) / 2 social interactions (equivalent to the task of counting the number of handshakes in a group of n people), that is, the complexity of the O (n 2 ) algorithm. It would seem that due to the fact that n / 2 pairs of people can simultaneously communicate, the time estimate is O (n) , but at real meetings only one person speaks at a time, therefore the worst case assessment is O (n 2 ) . If the interaction time is 5 minutes and it takes two iterations to reach full understanding in the group, then the meeting of three people will last 30 minutes, four hours, five will take 1 hour and 40 minutes to find a common solution (which is suspiciously like the truth). If the number of iterations depends on the number of participants, we get even more sad assessments.
')
But it is not all that bad!
- First, not all participants of the meeting can be independent and equal, they can form groups of interests (for example, the head and his two subordinates), then the discussion takes place not between individual participants, but between groups, of which there is always one person. A representative may change during the discussion, but he is always the only one. In this case, the complexity of social interaction is O ((n / m) 2 ) , where m is the average number of participants in each group present at the meeting.
- Secondly, O (n 2 ) is the worst estimate. It may turn out that each side expresses its position in turn, and each next one builds his statement taking into account everything he heard earlier. The last participant offers a solution to the problem - and all participants in the discussion agree with him or make their own minor changes. In this case, only 2n actions are enough to make a decision. Moral: a prepared presentation and a moderator defining the order of discussion can save a lot of time.
About (n * log (n)): working out a team decision through delegates. Often, making a decision requires a lot of people to be involved. The solution may cover a technically complex area or may require the efforts of a large number of people to implement. After the task is set, each of the participants offers a solution to their part of the task, setting it out to the delegate (for example, the head of his department). The delegate summarizes the received proposals and presents them to the delegate of the second level (selected among the delegates of the first level), who, in turn, summarizes the received proposals and presents them to the delegate of the third level - and so on. Continuing the algorithm recursively and reaching the person making the final decision, we will get an option that, to one degree or another, will take into account the opinion of each of the participants. And we get it quickly enough - due to the fact that communication with the delegate is perfectly parallel, we get the answer for O (m * log m (n)) , where m is the characteristic number of people in the group.
O (n): chain matching. Often the solution is already there, you just need to go through a standardized procedure for its approval. For example - to coordinate the addition of a new product on the shelf. Here, the complexity of one attempt will be equal to n , where n is the number of instances that will need to pass. Yes, the number of attempts is not limited in any way, but because requirements are known in advance, it is usually small.
About (n): alert. Ideal for situations where you need to bring some information unchanged to a large number of people. Each of the group will spend time on familiarization, so the effort will amount to n social interactions. In bad cases, the method may take the form "I ask you to familiarize yourself with the order and accept for execution", in good cases it is just a check for the correctness of the data, written in the code. The differences between these cases are in the number of people who actually encounter an alert (in the second, significantly less), as well as differences in the artist’s memory requirements (in the second, there’s no need to remember anything until the restriction works). But, personally, I like in this approach that it is O (1) in time for the sender - the labor costs will remain unchanged regardless of the number of people who receive the message. The dark side of the same rule - letters with dozens of people in a copy.
About (log (n)): notification through delegates. It is used when it is necessary to notify only one person, but it is not known who exactly. An example is a task that descends to management, then is transferred to the head of the department, then to the direct executor. An alternative way is to create a “single window” through which all tasks / orders / wishes are accepted. This way of setting the task is still constant in complexity for the sender, but much less labor-intensive for the receiving party, therefore it is the receiving party who, as a rule, initiates the change of the exchange method from “alert” to “alert via delegates”.
About (1): problem solving through a standard interface. The ideal situation to which, in my opinion, we must strive. The problem is known, as is the way to solve it, which means you can create an interface that will help a person solve his problem without any contact with other people, and the speed of solving the problem does not depend on the number of people who have encountered it. It can be said that this is the same “alert”, but from the point of view of the sender, and the real costs on the part of the users are still O (n) . This is true, but I decided to isolate this method, because, despite the mathematical equivalence, it gives a new look at the problem.
Are there ways of interacting with the outside world with complexity worse than O (n 2 ) ? Definitely yes - by analogy with the bog sorting you can come up with options that would be terribly impractical. I believe that they do not occur in practice just because all real problems are solved by less time-consuming algorithms.
If there are approaches in which the problem is solved in a constant time - then why do we need all the other methods? I believe that the main reason is freedom of decision making. Along with the improvement of the asymptotics, freedom gradually disappears. In a meeting of equal participants, the range of decisions is limited only to the powers of the people participating in the meeting. This tool is well suited for making important unique decisions. When using standard interfaces, the range of solutions is significantly narrowed.
Practical implications:
- Do not call to meetings of equal participants more than 5 people. If the time of one interaction between people is 5 minutes, most likely, you will not meet the 1 hour of discussion.
- do not call more than 15 people to meetings of unequal participants (5 heads + 2 subordinates from each side) - one hour is not enough for you again
-do not call to meetings people who only need “ok” - write a protocol on the results of the meeting and ask him to agree
- orders, instructions, informational messages (and, possibly, subsequent votes) is the only effective way to communicate if there are more than a few dozen stakeholders.
- if the department has more than 10 people - create a “single window” where standard requirements / wishes / requests will be received.
- if you or your employees do not have time to perform the tasks that come to them - think about whether you can improve the asymptotics by changing the way you interact with the outside world.
Ps Unfortunately, the speed of interaction between people does not double every two years.
Optimize your communication and be happy.
Source: https://habr.com/ru/post/336100/
All Articles