Вычислительная сложность

Автор темы svarog (Жолудь) 
ОбъявленияПоследний пост
ОбъявлениеРаботодателям и кадровым агентствам: Размещение вакансий и рекламы в форуме26.03.2008 03:07
ОбъявлениеРекомендации по использованию теха в нашем форуме15.04.2017 21:40
ОбъявлениеПравила и принципы форума «Высшая математика»28.10.2009 15:17
03.06.2019 22:28
Вычислительная сложность
Доброго времени суток.
Прошу помочь с определением вычислительной сложности решения задачи разложения произвольного нечетного числа $z$ на подмножество последовательных нечетных чисел, сумма которых равна исследуемому числу.
У данной задачи есть три варианта развития решения.
1) Меньший член подмножества последовательных нечетных чисел, сумма которых равна исследуемому числу $z$, равен единице. Тогда, решение задачи сведется к суммированию последовательных нечетных чисел, начиная с единицы, до достижения $z=k=1+3+5+…+ n_{i}$. Это вычислительно самый простой частный случай, алгоритм решения которого содержит наименьшее количество действий.
Рисунки на данном ресурсе не поддерживаются, поэтому приведу описание блок-схемы:
Блок_1 . . . . . . . . . . . . . . . $m=1,n=3,i=2,z,l=1$
. .переход к блоку_2
Блок_2 . . . . . . . . . . . . . . . $k=m+n$
. .переход к блоку_3
Блок_3 . . . . . . . . . . . . . . . если $z=k$, то переход $«да»$ к блоку_6, иначе переход $«нет»$ к блоку_4
. .переход «нет» от блока_3 к блоку_4
Блок_4 . . . . . . . . . . . . . . . $i=i+1,n=n+2$
. .переход к блоку_5
Блок_5 . . . . . . . . . . . . . . . $k=k+n$
. .переход от блока_5 к блоку_3
. .переход «да» от блока_3 к блоку_6
Блок_6 . . . . . . . . . . . . . . . вывод данных, конец алгоритма

2) Общий случай. В этом случае, в блок-схему алгоритма решения добавляется еще один критерий оценки состояния переменной $k$ по отношению к исследуемому числу $z$ и блок вычислений из трех действий. Суммирование последовательных нечетных чисел, начиная с единицы, продолжается до достижения $z<k=1+3+5+…+ n_{i}$, после чего происходит последовательное уменьшение суммы последовательных нечетных чисел на меньший член подмножества или прибавление следующего нечетного числа, в зависимости от проверки соотношения значений исследуемого числа $z$ и переменной $k$ после каждого блока вычислений. Вычисления будут продолжаться до тех пор, пока значение переменной $k$ не станет равным числу $z$. Этот вариант решения задачи содержит больше вычислительных действий, чем в первом варианте. В худшем случае, вычисления будут продолжаться до $i=3$, $n=((\frac{z}{3})-2)=n_{1}$, $n_{2}=n+2=(\frac{z}{3})$, $n_{3}= n_{2}+2=n_{max}=((\frac{z}{3})+2)$.
Описание блок-схемы:
Блок_1 . . . . . . . . . . . . . . . $m=1,n=3,i=2,l=1,z$
. .переход к блоку_2
Блок_2 . . . . . . . . . . . . . . . $k=m+n$
. .переход к блоку_3
Блок_3 . . . . . . . . . . . . . . . если $z=k$, то переход $«да»$ к блоку_9, иначе переход $«нет»$ к блоку_4
. .переход «нет» от блока_3 к блоку_4
Блок_4 . . . . . . . . . . . . . . . если $z>k$, то переход $«да»$ к блоку_7, иначе переход $«нет»$ к блоку_5
. .переход «нет» от блока_4 к блоку_5
Блок_5 . . . . . . . . . . . . . . . $k=k-l,i=i-1$
. .переход к блоку_6
Блок_6 . . . . . . . . . . . . . . . $l=l+2$
. .переход от блока_6 к блоку_3
. .переход «да» от блока_4 к блоку_7
Блок_7 . . . . . . . . . . . . . . . $i=i+1,n=n+2$
. .переход к блоку_8
Блок_8 . . . . . . . . . . . . . . . $k=k+n$
. .переход от блока_8 к блоку_3
. .переход «да» от блока_3 к блоку_9
Блок_9 . . . . . . . . . . . . . . . вывод данных, конец алгоритма

3) Частный случай, если вычисление алгоритма не останавливается при $i=3$, $n_{max}=((\frac{z}{3})+2)$ и продолжается до $i=1$, $k=n_{max}=z$. Вычислительно это самый сложный вариант решения задачи, поскольку проверяется в 3 раза больше значений переменной $k$. Но, при добавлении после блока_7 критерия проверки $n=((\frac{z}{3})+4)$, с остановкой выполнения алгоритма при его выполнении и выведением соответствующего сообщения, отсекаются лишние бессодержательные повторения вычислительных действий, уравниваются вычислительная сложность худшего случая решения задачи в общем случае и вычислительная сложность частного случая решения задачи.
Описание блок-схемы:
Блок_1 . . . . . . . . . . . . . . . $m=1,n=3,i=2,l=1,z$
. .переход к блоку_2
Блок_2 . . . . . . . . . . . . . . . $k=m+n$
. .переход к блоку_3
Блок_3 . . . . . . . . . . . . . . . если $z=k$, то переход $«да»$ к блоку_10, иначе переход $«нет»$ к блоку_4
. .переход «нет» от блока_3 к блоку_4
Блок_4 . . . . . . . . . . . . . . . если $z>k$, то переход $«да»$ к блоку_7, иначе переход $«нет»$ к блоку_5
. .переход «нет» от блока_4 к блоку_5
Блок_5 . . . . . . . . . . . . . . . $k=k-l,i=i-1$
. .переход к блоку_6
Блок_6 . . . . . . . . . . . . . . . $l=l+2$
. .переход от блока_6 к блоку_3
. .переход «да» от блока_4 к блоку_7
Блок_7 . . . . . . . . . . . . . . . $i=i+1,n=n+2$
. .переход к блоку_8
Блок_8 . . . . . . . . . . . . . . . если $n<((\frac{z}{3})+4)$, то переход $«нет»$ к блоку_11, иначе переход $«да»$ к блоку_9
. .переход «да» от блока_8 к блоку_9
Блок_9 . . . . . . . . . . . . . . . $k=k+n$
. .переход от блока_9 к блоку_3
. .переход «да» от блока_3 к блоку_10
Блок_10 . . . . . . . . . . . . . . . вывод данных, конец алгоритма
. .переход «нет» от блока_8 к блоку_11
Блок_11 . . . . . . . . . . . . . . . вывод данных, конец алгоритма

Конечным искомым решения задачи является определение количества $i$ членов подмножества последовательных нечетных чисел, дающих в сумме значение исследуемого числа $z$. В этом алгоритме решения задачи параллельно с началом выполнения решения производится только одно вычисление: находится значение $\frac{z}{3}$.
Решение задачи поиска подмножества последовательных нечетных чисел, сумма которых равна исследуемому числу $z$, можно реализовать и при помощи табличного приложения, например Excel. Создаются два столбца. В одном столбце, например $А$, ячейки заполняются сверху вниз последовательными нечетными числами по возрастанию от $1$ до $(( \frac{z}{3})+4)$ – для предотвращения лишних итераций в частном случае. В соседнем столбце, например $В$, в ячейки, кроме самой верхней, вписываются формулы. Так, пусть ячейка $А1$ – пустая, в ячейке $В1$ записывается значение $z$. Тогда, $А2=1$, $А3=3$, $А4=5$ и так далее. В остальные ячейки столбца $В$ записывается формула $«=(ячейка сверху)минус(ячейка слева)»$. В ячейке $В2$ записывается формула $«=В1-А2»$, в ячейке $В3$ записывается $«=В2-А3»$, и так далее. После формирования столбцов выполняются формулы и проверяется, принимает ли какая-либо ячейка в столбце $В$ значение $«ноль»$. Если $«да»$, то вычисления закончены - это вариант_1 развития решения задачи,- определяется количество не пустых ячеек в столбце $А$ от строки, в которой формула в ячейке столбца $В$ приняла значение $«ноль»$, и в вверх до ячейки $А1$ включительно. Иначе, продолжается поиск последовательных нечетных чисел, сумма которых равна исследуемому числу $z$. Для этого удаляется самое верхнее, наименьшее нечетное число в столбце $А$ и проверяется, принимает ли какая-либо ячейка в столбце $В$ значение $«ноль»$. Если $«да»$, то вычисления закончены, если $«нет»$, то удаление верхнего нечетного в столбце $А$ и проверка столбца $В$ повторяется до тех пор, пока какая-либо ячейка в столбце $В$ примет значение $«ноль»$ либо до удаления последнего нечетного числа в столбце $А$, равного $((\frac{z}{3})+4)$ – что значит, что переменная $i=1$. С помощью макросов весь описанный процесс в табличном приложении Excel полностью программируется и выполняется автоматически.
Также этот алгоритм можно выполнять в табличном приложении Excel в более развернутом виде.
Для удобства пользователя, верхние три строки закрепляются. Сначала, ставим рабочие пометки: в ячейке $C1$ пишем «z», в ячейке $E1$ пишем «-», в ячейке $G1$ пишем «+», в ячейке $I1$ пишем «z-+». Затем:
- в ячейку $C2$ записываем исследуемое число $z$;
- в ячейку $E2$ записываем формулу «=сумм(D:D)» - формула возвращает сумму всех чисел в ячейках столбца $D$;
- в ячейку $G2$ записываем формулу «=сумм(F:F)» - формула возвращает сумму всех чисел в ячейках столбца $F$;
- в ячейку $I2$ записываем формулу «=C2-E2+G2» - формула уменьшает исследуемое число на величину суммы чисел в ячейках столбца $D$ и увеличивает полученную разницу на величину суммы чисел в ячейках столбца $F$ – основной вычислительный процесс;
- в ячейку $E3$ записываем формулу «=счёт(D:D)» - формула возвращает количество не пустых ячеек столбца $D$;
- в ячейку $G3$ записываем формулу «=счёт(F:F)» - формула возвращает количество не пустых ячеек столбца $F$;
- в ячейку $I3$ записываем формулу «=E3-G3» - формула считает разницу между количеством не пустых ячеек столбца $D$ и количеством не пустых ячеек столбца $F$;
- в ячейку $K3$ записываем формулу «=E3+G3» - формула считает суммарное количество не пустых ячеек столбца $D$ и не пустых ячеек столбца $F$.
Данный вариант реализации алгоритма решения исследуемой задачи более информативен, чем рассматриваемый ранее, и позволяет, как избежать постоянного перемещения от начала подмножества последовательных нечетных чисел в его конец, опять в начало и так далее, так и отсечь, при необходимости, вспомогательные вычислительные действия, выполняемые параллельно основному вычислительному процессу.
Для выполнения решения, в ячейки столбца $D$ в порядке сверху вниз вносятся последовательные нечетные числа, в порядке возрастания, начиная с единицы, до тех пор, пока в ячейке $I2$ не появится $ноль$, либо $отрицательное число$. Если на данном этапе выполнения решения в ячейке $I2$ появится $ноль$, значит, исследуемое число $z$ имеет целое значение корня квадратного, и значения в ячейках будут иметь следующий вид: $E3=I3=K3$ – они будут равны значению корня квадратного из числа $z$, в ячейке $G3=0$. Если же на данном этапе выполнения решения в ячейке $I2$ появится $отрицательное число$, то в ячейки столбца $F$ в порядке сверху вниз вносятся последовательные нечетные числа, в порядке возрастания, начиная с единицы, до тех пор, пока в ячейке $I2$ не появится $ноль$, либо $положительное число$. Теперь получение $нуля$ в ячейке $I2$ будет свидетельствовать о нахождении таких значений, при которых $(C2=z)=(E2-G2)$. В дальнейшем решении выполняется правило: если в ячейке $I2$ появится $отрицательное число$, то вносим в следующую по порядку ячейку столбца $F$ следующее по порядку нечетное число, если в ячейке $I2$ появится $положительное число$, то вносим в следующую по порядку ячейку столбца $D$ следующее по порядку нечетное число. Так должно продолжаться до появления в ячейке $I2$ $нуля$, свидетельствующего об окончании вычислений, или до появления в ячейке $I3=y$ значения $2$, свидетельствующего о том, что исследуемое число $z$ является простым, и дальнейшие вычисления нецелесообразны.
Как видно из описания выполняемых действий, вычислительная сложность решения задачи поиска подмножества последовательных нечетных чисел, сумма которых равна исследуемому числу $z$, по сути, одинакова для различных вариантов развития решения:
1) Если исследуемое число $z$ имеет целое значение корня квадратного. В этом случае от исследуемого числа $z$ будет $I3=y=K3=x=\sqrt{z}$-раз выполненено вычитание.
2) Если исследуемое число $z$ не имеет целое значение корня квадратного. В этом случае от исследуемого числа $z$ будет $K3=x$-раз выполнено вычитание и сложение.
3) В случаях, если исследуемое число $z$ оказывается простым числом, продолжительность вычислений, количество вычислительных действий, зависит от того, как настроен стоп-маркер. Это может быть значение $c=((\frac{z}{3})+4)$, либо появление в ячейке $I3=y$ значения $2$, либо что-либо еще. В любом случае, вычислительная сложность данного варианта решения будет порядка $\frac{z}{3}+2$.



Редактировалось 3 раз(а). Последний 13.07.2019 16:23.
04.06.2019 14:46
хм
Цитата
svarog (Жолудь)
задачи разложения исследуемого числа $z$ на подмножество последовательных нечетных чисел, сумма которых равна исследуемому числу.

разложите, например, 6.
04.06.2019 18:35
ой
недосмотрел, пропустил, прошу простить за неточность!
Вместо:"... разложения исследуемого числа... " необходимо было вставить:"... разложения произвольного нечетного числа ...". Не глядя скопировал из черновика. Сейчас отвечу Вам и исправлю в тексте.
Конкретно четное число 6, как и большинство четных, не поддается данному процессу. В задаче рассматриваются только нечетные числа - это важно.
Примеры:
3=3
4=1+3
5=5
7=7
8=3+5
9=1+3+5
. . .
15=3+5+7
16=1+3+5+7
04.06.2019 22:06
хм
любое нечетное число раскладывается на ряд нечетных чисел из единственного члена - самого себя.
05.06.2019 11:10
Призыв топикстартера
помочь ему носить воду решетом выглядит изощренным издевательством. Психи не должны требовать у здоровых людей помощи в написании своих бредней.
05.06.2019 19:36
Да,
уважаемый zklb (Дмитрий), это бесспорно.
Но, кроме названной Вами комбинации, для большинства нечетных чисел существует набор из трёх и более последовательных нечетных чисел, сумма которых равна исследуемому числу.
06.06.2019 17:39
хм
Цитата
svarog (Жолудь)
уважаемый zklb (Дмитрий), это бесспорно.
Но, кроме названной Вами комбинации, для большинства нечетных чисел существует набор из трёх и более последовательных нечетных чисел, сумма которых равна исследуемому числу.

так и в чем задача то?
06.06.2019 19:35
Так...
Так ведь вот, второе предложение:
Цитата
svarog (Жолудь)
... Прошу помочь с определением вычислительной сложности решения задачи разложения произвольного нечетного числа $z$ на подмножество последовательных нечетных чисел, сумма которых равна исследуемому числу. ...
Это и есть задача, с решением которой я прошу помочь. И далее идёт описание всех возможных вариантов развития решения для определения случая с максимальной вычислительной сложностью, чтобы заинтересовавшиеся и решившиеся на помощь не тратили время на это.
А если Вы имели в виду "для чего всё это - ... разложения ... , ... последовательных ... , ... сумма ..., - делать?",- то ответ на этот вопрос не поможет получить ответ на заданный выше (и процитированный здесь) вопрос. И даже наоборот. Ответ на вопрос о вычислительной сложности задан здесь чтобы определить, стоит ли это делать.
Я же не принуждаю кого-либо что-то делать. Не интересно, не понимаете зачем тратить на это время - не тратьте. Заинтересовались, можете помочь - помогите.
28.06.2019 09:52
Суммы
Суммы последовательных нечетных чисел определенные как факториал
1+3+5+7+9
4, 9, 16, 25

Алгоритм невозможен в принципе.
29.06.2019 01:53
простые числа
для вашей задачи надо пока найти хотя бы одну функцию для ее решения а потом не трудно найти все такие функции
29.06.2019 16:35
хм...
Цитата
valeret
Суммы последовательных нечетных чисел определенные как факториал
1+3+5+7+9
4, 9, 16, 25

Алгоритм невозможен в принципе.
Если не брать во внимание то, что я описал блок-схему алгоритма (да, как смог, с графикой на этом ресурсе печалька), а так же привел пример решения с помощью Excel'я... Даже и не знаю, что Вы воспримете как контраргумент... Прошу немного подождать, в течении недели-другой выложу здесь описание на несколько измененном Excel'евском примере, почему вычислительная сложность решения данной задачи в общем случае составляет $x$ сложений-вычитаний, при $z=x*y$, $x>y$.
А пока я не выложил эту информацию, можете, если захотите, поискать опытным путем нечетное число, которое нельзя было бы представить в виде суммы последовательных нечетных чисел. Приведу несколько примеров:
5=5 - простое число
7=7 - простое число
9=1+3+5
11=11 - простое число
13=13 - простое число
15=3+5+7
17=17 - простое число
19=19 - простое число
21=5+7+9
23=23 - простое число
25=1+3+5+7+9
27=7+9+11
. . .
243=19+21+23+25+27+29+31+33+35=79+81+83
29.06.2019 19:53
проще не бывает
1) факторизация нечетного числа
2) определяем минимальный простой делитель - это и есть минимальное число слагаемых суммы .
3) определяем среднее значение слагаемых
4) распределяем эти слагаемые по возрастанию с разностью 2
5) центральный вычет остается средним слагаемым
Примечание
"Минимальный" делитель может быть и не простым., тогда число слагаемых увеличится



Редактировалось 1 раз(а). Последний 29.06.2019 22:15.
30.06.2019 00:56
простые числа
Цитата
vorvalm
1) факторизация нечетного числа
2) определяем минимальный простой делитель - это и есть минимальное число слагаемых суммы .
3) определяем среднее значение слагаемых
4) распределяем эти слагаемые по возрастанию с разностью 2
5) центральный вычет остается средним слагаемым
Примечание
"Минимальный" делитель может быть и не простым., тогда число слагаемых увеличится

бред для факторизации существуют специальные функции которые упорядоченно изоморфно разлагают любое число
30.06.2019 16:51
да
Цитата
vorvalm
1) факторизация нечетного числа
2) определяем минимальный простой делитель - это и есть минимальное число слагаемых суммы .
3) определяем среднее значение слагаемых
4) распределяем эти слагаемые по возрастанию с разностью 2
5) центральный вычет остается средним слагаемым
Примечание
"Минимальный" делитель может быть и не простым., тогда число слагаемых увеличится
да, я понимаю, что Вам это может показаться голословным утверждением, но, при разложении произвольного нечетного числа на сумму последовательных нечетных чисел, количество членов найденного подмножества всегда равно меньшему составляющему множителю. Поэтому иногда возможны несколько вариантов представления числа в виде суммы последовательных нечетных. И да, это всё математически доказуемо.
30.06.2019 17:36
проще не бывает
Вы не обратили внимания на примечание.
Это возможно, если нечетное число N имеет более 2-х простых делителей., причем
число представлений равно числу делителей, меньших √ N



Редактировалось 1 раз(а). Последний 30.06.2019 19:38.
30.06.2019 19:44
произвольная
Цитата

Меньший член подмножества последовательных нечетных чисел, сумма которых равна исследуемому числу z, равен единице.

27=7+9+11
243=79+81+83

Тогда последовательность суммы произвольная а не 1.3.5 и алгоритм сводится к проверке числа на целое деление на нечетный делитель 3, 5, 7....
08.07.2019 08:10
Да,
Цитата
valeret
Цитата

Меньший член подмножества последовательных нечетных чисел, сумма которых равна исследуемому числу z, равен единице.

27=7+9+11
243=79+81+83

Тогда последовательность суммы произвольная а не 1.3.5 и алгоритм сводится к проверке числа на целое деление на нечетный делитель 3, 5, 7....

меньший член подмножества последовательных нечетных чисел, сумма которых равна исследуемому числу z, равен единице - это у чисел, имеющих целое значение корня квадратного. Для остальных меньший член подмножества последовательных нечетных чисел будет больше единицы, но нечетные числа в подмножестве остаются последовательными, по возрастанию от меньшего без пропусков.
08.07.2019 08:11
дополнил
Дополнил статью.
Также этот алгоритм можно выполнять в табличном приложении Excel в более развернутом виде.
Для удобства пользователя, верхние три строки закрепляются. Сначала, ставим рабочие пометки: в ячейке $C1$ пишем «z», в ячейке $E1$ пишем «-», в ячейке $G1$ пишем «+», в ячейке $I1$ пишем «z-+». Затем:
- в ячейку $C2$ записываем исследуемое число $z$;
- в ячейку $E2$ записываем формулу «=сумм(D:D)» - формула возвращает сумму всех чисел в ячейках столбца $D$;
- в ячейку $G2$ записываем формулу «=сумм(F:F)» - формула возвращает сумму всех чисел в ячейках столбца $F$;
- в ячейку $I2$ записываем формулу «=C2-E2+G2» - формула уменьшает исследуемое число на величину суммы чисел в ячейках столбца $D$ и увеличивает полученную разницу на величину суммы чисел в ячейках столбца $F$ – основной вычислительный процесс;
- в ячейку $E3$ записываем формулу «=счёт(D:D)» - формула возвращает количество не пустых ячеек столбца $D$;
- в ячейку $G3$ записываем формулу «=счёт(F:F)» - формула возвращает количество не пустых ячеек столбца $F$;
- в ячейку $I3$ записываем формулу «=E3-G3» - формула считает разницу между количеством не пустых ячеек столбца $D$ и количеством не пустых ячеек столбца $F$;
- в ячейку $K3$ записываем формулу «=E3+G3» - формула считает суммарное количество не пустых ячеек столбца $D$ и не пустых ячеек столбца $F$.
Данный вариант реализации алгоритма решения исследуемой задачи более информативен, чем рассматриваемый ранее, и позволяет, как избежать постоянного перемещения от начала подмножества последовательных нечетных чисел в его конец, опять в начало и так далее, так и отсечь, при необходимости, вспомогательные вычислительные действия, выполняемые параллельно основному вычислительному процессу.
Для выполнения решения, в ячейки столбца $D$ в порядке сверху вниз вносятся последовательные нечетные числа, в порядке возрастания, начиная с единицы, до тех пор, пока в ячейке $I2$ не появится $ноль$, либо $отрицательное число$. Если на данном этапе выполнения решения в ячейке $I2$ появится $ноль$, значит, исследуемое число $z$ имеет целое значение корня квадратного, и значения в ячейках будут иметь следующий вид: $E3=I3=K3$ – они будут равны значению корня квадратного из числа $z$, в ячейке $G3=0$. Если же на данном этапе выполнения решения в ячейке $I2$ появится $отрицательное число$, то в ячейки столбца $F$ в порядке сверху вниз вносятся последовательные нечетные числа, в порядке возрастания, начиная с единицы, до тех пор, пока в ячейке $I2$ не появится $ноль$, либо $положительное число$. Теперь получение $нуля$ в ячейке $I2$ будет свидетельствовать о нахождении таких значений, при которых $(C2=z)=(E2-G2)$. В дальнейшем решении выполняется правило: если в ячейке $I2$ появится $отрицательное число$, то вносим в следующую по порядку ячейку столбца $F$ следующее по порядку нечетное число, если в ячейке $I2$ появится $положительное число$, то вносим в следующую по порядку ячейку столбца $D$ следующее по порядку нечетное число. Так должно продолжаться до появления в ячейке $I2$ $нуля$, свидетельствующего об окончании вычислений, или до появления в ячейке $I3=y$ значения $2$, свидетельствующего о том, что исследуемое число $z$ является простым, и дальнейшие вычисления нецелесообразны.
Как видно из описания выполняемых действий, вычислительная сложность решения задачи поиска подмножества последовательных нечетных чисел, сумма которых равна исследуемому числу $z$, по сути, одинакова для различных вариантов развития решения:
1) Если исследуемое число $z$ имеет целое значение корня квадратного. В этом случае от исследуемого числа $z$ будет $I3=y=K3=x=\sqrt{z}$-раз выполнено вычитание.
2) Если исследуемое число $z$ не имеет целое значение корня квадратного. В этом случае от исследуемого числа $z$ будет $K3=x$-раз выполнено вычитание и сложение.
3) В случаях, если исследуемое число $z$ оказывается простым числом, продолжительность вычислений, количество вычислительных действий, зависит от того, как настроен стоп-маркер. Это может быть значение $c=((\frac{z}{3})+4)$, либо появление в ячейке $I3=y$ значения $2$, либо что-либо еще. В любом случае, вычислительная сложность данного варианта решения будет порядка $\frac{z}{3}+2$.



Редактировалось 1 раз(а). Последний 13.07.2019 16:20.
12.07.2019 10:05
простые числа
а если просто подставит формула какая будет вычислительная сложность ?
13.07.2019 16:16
так вот же:
вот же написано
Цитата
svarog (Жолудь)
:
1) Если исследуемое число $z$ имеет целое значение корня квадратного. В этом случае от исследуемого числа $z$ будет $I3=y=K3=x=\sqrt{z}$-раз выполнено вычитание.
2) Если исследуемое число $z$ не имеет целое значение корня квадратного. В этом случае от исследуемого числа $z$ будет $K3=x$-раз выполнено вычитание и сложение.
3) В случаях, если исследуемое число $z$ оказывается простым числом, продолжительность вычислений, количество вычислительных действий, зависит от того, как настроен стоп-маркер. Это может быть значение $c=((\frac{z}{3})+4)$, либо появление в ячейке $I3=y$ значения $2$, либо что-либо еще. В любом случае, вычислительная сложность данного варианта решения будет порядка $\frac{z}{3}+2$.



Редактировалось 1 раз(а). Последний 13.07.2019 16:21.
Извините, только зарегистрированные пользователи могут публиковать сообщения в этом форуме.

Кликните здесь, чтобы войти