Ben tamsayılar tekrarlayabilir Sıralanmış dizide, içinde x daha büyük ilk tamsayı bulacaksınız bir algoritma, yazmak gerekir. algoritma o küçük O (n), karmaşıklığı sahip olmalıdır. O (n) bir O (n) zorlukla algoritmaları arasında fark nedir?
O-küçük (n) karmaşıklığı ile önce büyük tam sayıyı bulmak için algoritma
Sen ilk büyük tamsayı bulmak için ikili arama yöntemi kullanarak yapabilirsiniz
x. Bu yaptığınız
O(log(n)) = small_o(n).
insanlar benden önce belirttiğimiz gibi, bir ikili arama yapmak istiyorum. Bu yayın, örneğin kodu:
Python'da bu kenarortay fonksiyonu ile en kolay: https://docs.python.org/2/library/bisect.html
from bisect import bisect_right def find_gt(a, x): 'Find leftmost value greater than x' i = bisect_right(a, x) if i != len(a): return a[i] raise ValueError
: Burada çok iyi ve az-o notasyonu vs büyük-o derinliği açıklamasında olan Big-O ve Küçük-O gösterimi arasındaki fark
En basit ama etkili bir algoritma @OmG bahsedildiği gibi İkili Arama ve burada başlatmak için link: https://en.wikipedia.org/wiki/Binary_search_algorithm
Fikri oldukça basittir: Sadece orta size, sağ yarıda bulmalıyız aşikardır Numarana altında olması durumunda size, dizinin orta eleman ile arama numarasını ... aksi sol yarısı karşılaştırın. Sadece bir unsur olduğunda sen dur.