По моим подсчетам количество итераций в цикле в алгоритме равно числу, оооочень похожему на число Фибоначи от длины массива. Если например будет массив с 4 элементами, количество итераций в цикле будет равно: 0+1=1, 1+2=3, 3+3=6, где во всех выражениях первое слагаемое - количество итерация на данный момент, а второе - индекс от 1 до (длинны массива)-1. Я не знаю, может подобному считыванию есть название, но мой вопрос: как выразить время работы этого алгоритма в О-большой? Также позже я посчитал, что количество итераций приблизительно равно (длина массива в квадрате)/2, можно ли таким образом записать, что время работы алгоритма равно О(N^2/2)?
Lynn «Кофеман», не имеет значения? Ну это ж довольно сильно уменьшает любое значение. Это же минус 50 процентов от любого числа. Это же тоже ведь экспоненциально, ибо частное от делимого меняется в зависимости от размера делимого. Алгоритм скоро внесу.
Lynn «Кофеман»,
код на Пайтоне. На вход всегда идёт список, первым элементом которого будет количество точек на координатной плоскости, где первое число в списке внутри списка после первого элемента всегда x, а второе - y. Программа должна вывести количество отрезков, у которых выполняется два условия:
1.Любой конец отрезка не должен лежать на одной из осей
2. Отрезок должен пересекать обе оси
Я просто в качестве примера заранее ввёл числа в список, в идеале их вводит пользователь, но дело в другом.
Отрезок опирается на одну из осей, если одна ось из точек будет равна 0, вот я и записал условие, что при x или y, равном нулю хоть у какой-то точки, цикл просто запустит следующую итерацию.
Далее, отрезок пересекает обе оси только в случае, если координаты первой точки будут либо отрицательны, либо положительны в отличии от второй точки(то есть, если одна точка будет (-4:4, а вторая 3:-5, или первая будет (4;4), а вторая (-4:--5,), то переменная v увеличится на 1.
a = [5, [4,3], [-3,-5], [0,5], [2,0], [-2,5], [2,0], [5,-2], [-4,5]]
v = 0
for i in range(1,len(a)):
if a[i][0] == 0 or a[i][1] == 0:
continue
for j in range(i+1,len(a)):
if a[j][0] == 0 or a[j][1] == 0:
continue
if (a[i][0]<0 and a[j][0]>0) or (a[i][0]>0 and a[j][0]<0):
if (a[i][1]<0 and a[j][1]>0) or (a[i][1]>0 and a[j][1]<0):
v+=1
Можно ли как-то оптимизированнее сделать код? Если что, задача из ЕГЭ по информатике. Говорю сразу, в Пайтоне я даже хуже чайника, я знаю необходимый минимум для задач, так что не очень сильно ругать.
Bavashi, начало координат вы имеете в виду точку (0;0)? Почему не учитывать? Они считаются за отрезки, прошедшие через обе оси, ибо касаются их обеих, а если вы про то, что конец отрезка лежит на оси, то нет, среди этих точек нет координатов с нулем где либо.
Lynn «Кофеман», всмысле, не нужны отрезки? Я ж говорю, нужны конкретно отрезки, то есть две точки с определёнными координатами. Алгоритм подбирает первую точку и ищет среди всех остальных точек ту, которая при соединении с ней даст нужный результат.
Lynn «Кофеман», да на чём угодно, кроме нулевого значения любой координаты. А концы отрезков, проходящие через обе оси подсчитать, как я говорил, я смог только методом, что координаты первой точки противоположны второй по знакам(либо положительное, либо отрицательное). Я не знаю, как это можно подсчитать по другому.
@Bavash, а зачем там переменные mid, lefthalf и righthalf? Там все равно во всех элементах кроме первого только по два элемента, так что можно просто было написать:
recurPointFind(0)
recurPointFind(1)
И, пока я не проверял ваш алгоритм, но думаю, что он не выдаст нужного.
Bavashi, ну вообще не особо, у меня проблемы с ее пониманием небольшие. Я слышал про алгоритм сортировки слиянием, я о нем читал, причем долго, однако, до меня не дошло, опять таки, потому, что я плохо разбираюсь в рекурсии.
Bavashi, 12LiCaNtRoP12, раз уж меня призвали, то отвечу. Согласно условию "ни один конец не лежит на оси, отрезок пересекает обе оси" - однозначно следует что все 4 координаты у искомого отрезка ненулевые. Раз он пересекает ось x - то знаки у y-координат разные. Так же по оси y. В итоге получаем, что надо подсчитать пары точек, у которых знаки x и y разные. Это делается за линейную сложность просто подсчитав 4 числа - сколько точек в каждом из квадрантов (строго внутри, не считая осей). После надо сложить произведения чисел для противостоящих квадрантов.
Исходя из такой реализации это может быть и два метода или два прохода, что не будет являться линейной сложностью.
Вы это серъезно? Вы либо что-то непоняли, либо совсем не понимаете сложности алгоритмов. Делаете ли вы 2, 3 или 1 проход по списку - сложность все-равно линейная. Можно разбить цикл на 2, иногда - объединить 2 последовательных цикла. Один фиг - сложность будет линейная. Только реализация с несколькими циклами будет немного медленее, потому что проверки конца цикла и инкриминирование счетчика будет происходить в 2 раза больше. Но это замедление на константное количество процентов, не зависящее от n. По умному говоря, у решений будут разные константы. Хоть и различающиеся на несколько процентов.
пересекающиеся отрезки - оси координат. Отрезки пересекающие две оси координат.
Да. давайте повторю целиком, чтобы не было недопонимания. Мы решаем задачу - найти сколько отрезков с концами в заданных точках пересекают обе оси координат и не лежат ни одним концом на них.
Проверка на малых числах не всегда работает. там фибоначи, квадрат и черт знает что похожи.
Если у вас там что-то вроде for "i=1...n do for j = i..n do" или каике-то еще 2 вложенных цикла, где внутренняя переменная бежит от или до внешней переменной, то точное количество итераций будет n(n+1)/2, что есть O(N^2).
Нет, моя итерация выглядит так:
for i in range(1,len(N)):(тут сделать отступ от начала нельзя, так что просто считайте, что следующая строка - это цикл внутри цикла)
for j in range(i+1,len(N):
Там, ведь, получается, что цикл внутри цикла вызывается на 1 раз меньше каждый раз, когда происходит первый цикл.
Кстати, я еще посчитал, при таком раскладе количество итераций будет приблизительно вдвое меньше, чем длина массива в квадрате при любом значении.
Например, при длине 1000 количество итераций будет равно около 495000, а длина в массива в квадрате при этом равна 1000000.